Проблема с различием & и and. Как работает алгоритм проверки на степень двойки?
Задача:
Учитывая целое число 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, то результат будет некорректный, почему?
Ответы (2 шт):
and является логическим оператором, тогда как & - побитовым И
Пример:
>>> x = 0b0101
>>> x
5
>>> y = 0b0110
>>> y
6
>>> z = x & y
>>> z
4
>>> # 0b0100 - 4 в двоичном виде
>>>
>>> z = x and y
>>> z
6
Как это работает:
K-я степень двойки в двоичном виде выглядят как один единичный бит на k-м месте 00001000. Если отнять единицу, то получится число с k единичными битами 00000111. При побитовом & таких чисел всегда выйдёт ноль.
00001000
&
00000111
---------
00000000
Поэтому выражение (n & n - 1) == 0 можно использовать для определения, является ли n степенью двойки. В данном случае для получения True используется обратное выражение и логическое отрицание not.
Нужно также учесть случай, когда само n==0, поэтому два выражения объединяются логическим and