Проблема с различием & и and. Как работает алгоритм проверки на степень двойки?

Рейтинг: 1Ответов: 2Опубликовано: 28.02.2023

Задача:

Учитывая целое число n, вернуть True если это степень двойки. В противном случае возвращайтесь False.

Пример 1:

Вход: n = 1
 Выход: правда
 Объяснение: 2 ** 0 = 1

Пример 2:

Ввод: n = 16
 Вывод: верно
 Объяснение: 2 ** 4 = 16

Пример 3:

Вход: n = 3
 Выход: ложь

Проблема

Задачу я решил, но увидел решение другого человека. ->

def isPowerOfTwo(self, n: int) -> bool:
    return n and not (n & n - 1)

Как это работает? А также вопрос будет: если мы заменим & на and, то результат будет некорректный, почему?

python python-3.x алгоритм функции
Источник: Stack Overflow на русском

Ответы

▲ 5Принят

Как это работает:

K-я степень двойки в двоичном виде выглядят как один единичный бит на k-м месте 00001000. Если отнять единицу, то получится число с k единичными битами 00000111. При побитовом & таких чисел всегда выйдёт ноль.

 00001000
& 
 00000111
---------
 00000000

Поэтому выражение (n & n - 1) == 0 можно использовать для определения, является ли n степенью двойки. В данном случае для получения True используется обратное выражение и логическое отрицание not.

Нужно также учесть случай, когда само n==0, поэтому два выражения объединяются логическим and

▲ 1

and является логическим оператором, тогда как & - побитовым И

Пример:

>>> x = 0b0101
>>> x
5
>>> y = 0b0110
>>> y
6
>>> z = x & y
>>> z
4
>>> # 0b0100 - 4 в двоичном виде
>>>
>>> z = x and y
>>> z
6