Является ли заданное число степенью числа 2?

Фото Янко Ферлич на Unsplash

В этом уроке мы попытаемся проверить, является ли заданное число степенью двойки. Мы решим это, написав эффективный алгоритм, который занимает оптимальное количество времени.

Введение

Давайте зададим еще один сложный вопрос, чтобы проверить ваше понимание побитовых операторов.

Пример 01:

```javascript

Вход: 4

Вывод: True (поскольку 4 равно 2 ^ 2)

Пример 02:

```javascript

Вход: 12

Выход: Ложь

Постановка задачи

Напишите программу, которая проверяет, является ли заданное число степенью двойки или нет.

Давайте рассмотрим число и найдем, как это делает оператор И.

```javascript

Ввод = 64

Выход: правда

Объяснение

Мы решаем эту проблему, используя оператор & в компьютерах. Есть много способов решить эту проблему, два из которых являются простыми, а один — более сложным, но лучшим решением.

Предположим, что n неотрицательно. Для этого мы используем оператор &.

Решение: метод грубой силы/наивный подход

Подсказка. Самое интересное в вычислении степени двойки состоит в том, что у них количество установленных битов равно единице.

Алгоритм

1. Прочитайте введенное значение.

1. Несколько раз разделите ввод с помощью «2».

• если n не равно 1 и если оно нечетно, мы вернем false.

• иначе истина.

Вот как будет выглядеть наш алгоритм:

Код

```javascript

экспортировать const IsEven = (n: число): логическое значение => {

вспомогательная функция (значение: число): логическое {

если (значение === 0) {

вернуть ложь;

в то время как (значение! == 1) {

если (значение % 2 !== 0) {

вернуть ложь;

значение >>= 1;

вернуть истину;

вернуть помощник(n);

console.log(IsEven(6));

console.log(IsEven(8));

Анализ сложности

Временная сложность: O(logn)

Это требует сложности log(n). Мы можем работать лучше за постоянное время, используя алгоритм Брайана Кернигана.

Пространственная сложность: O(1)

Пространственная сложность O(1). Он не выделял дополнительного места.

Упражнение по кодированию

Сначала просмотрите приведенные выше фрагменты кода и придумайте решение. Эта задача предназначена для вашей практики, поэтому попробуйте сначала решить ее самостоятельно. Если вы застряли, вы всегда можете обратиться к решению, представленному в разделе решений. Удачи!

```javascript

экспорт const isPow2 = (n: число): логическое значение => {

// Пишите - Ваш - Код- Здесь

вернуть ложь; // изменить это, вернуть true/false на основе входных данных

Если у вас есть ответ, отлично! Если нет, это нормально, попрактикуйтесь в подобных задачах, и вы хорошо освоите трюки с битовыми манипуляциями.

Я объясню решение ниже.

Давайте посмотрим, как мы используем алгоритм Брайана Кернигана для достижения этой цели.

Обзор решения: алгоритм Брайана Кернигана

Это считается быстрее, чем предыдущий наивный подход.

В этом подходе мы подсчитываем установленные биты. Если число является степенью двойки, мы знаем, что в его двоичном представлении присутствует только один установленный бит.

В двоичном коде мы идем справа налево со степенью двойки.

Например:

2^0, 2^1, 2^2, 2^3, 2^4 и так далее.

Алгоритм

Прежде чем говорить об алгоритмических шагах, просмотрите табличную форму шагов, изображающих алгоритм.

1. Если (n & (n - 1) == 0), вернуть True.

1. иначе Ложь.

Давайте визуализируем значения в таблице ниже:

Давайте посмотрим на пару примеров:

```java

n = 4 => 00000000 00000000 00000000 00000100

п - 1 = 3 => 00000000 00000000 00000000 00000011

(n & (n - 1)) = 0 => 00000000 00000000 00000000 00000000

(n&(n - 1)), здесь это становится 0, что является истиной. Следовательно, число «4» является степенью числа 2.

```java

n = 6 => 00000000 00000000 00000000 00000110

п - 1 = 5 => 00000000 00000000 00000000 00000101

(n & (n - 1)) = 4 => 00000000 00000000 00000000 00000100

(n&(n - 1)) равно 4, что не равно 0. Следовательно, число «6» не является степенью числа 2.

Рассмотрим оптимизированный подход.

Код

Вот причина этого решения.

```javascript

экспортировать const IsEven = (n: число): логическое значение => {

вспомогательная функция (значение: число): логическое {

если (значение === 0) {

вернуть ложь;

возврат (значение & (значение - 1)) === 0;

вернуть помощник(n);

console.log(IsEven(6));

console.log(IsEven(8));

Мы можем еще больше упростить этот код до одной строки, показанной ниже.

```javascript

const IsEven = (n: число): логическое значение => {

вернуть n !== 0 && (n & (n - 1)) === 0;

console.log(IsEven (6));

console.log(IsEven (8));

Анализ сложности

Временная сложность: O(1)

Время выполнения зависит от количества «1-битов» в «n». В худшем случае все биты в n являются 1-битами. С 32-битным целым числом время выполнения составляет O(1).

Пространственная сложность: O(1)

Пространственная сложность O(1). Он не выделял дополнительного места.

Дополнительно

Если вы заинтересованы в освоении битовых трюков, у меня есть курс, который понравился более чем 100 тысячам программистов.

В этом курсе вы узнаете, как решать проблемы, используя манипуляции с битами, мощную технику, которая может оптимизировать ваши алгоритмические навыки и навыки решения проблем. В курсе есть простое объяснение со схемами, подробными пошаговыми рисунками и различными способами решения с помощью побитовых операторов.

Эти битовые трюки могут помочь в соревновательном программировании и собеседованиях по кодированию при запуске алгоритмов, в основном за время O (1).

Это одна из самых важных/критических тем, когда кто-то готовится к собеседованию по программированию для компаний FAANG (Facebook, Amazon, Apple, Netflix и Google).

Для начала вы начнете с изучения системы счисления и того, как она представлена. Затем вы перейдете к изучению шести различных побитовых операторов: AND, OR, NOT, XOR и битового сдвига. На протяжении всего курса вы получите массу практического опыта, работая над практическими задачами, чтобы улучшить свое понимание.

К тому времени, когда вы закончите этот курс, вы будете решать проблемы быстрее и эффективнее!! 🤩

Ссылка на мой курс: [Master Bit Manipulation for Coding Interviews] (https://www.educative.io/courses/bit-manipulation?aff=xjzd).

Совместно опубликовано [здесь] (https://ggorantala.dev/power-of-two-a-google-interview-question-java-solution?x-host=ggorantala.dev).