Запрос о том, является ли число степенью 2

Question

Использование классического фрагмента кода:

if (x & (x-1)) == 0

Если ответ 1, то он ложный, а не степень 2. Однако работа с 5 (не степень 2) и 4 приводит к:

0001 1111 0001 1111 0000 1111

Это 4 1 с.

Работает на 8 и 7:

1111 1111 0111 1111

0111 1111

Сначала 0, но мы имеем 4.

В этой ссылке (http://www.exploringbinary.com/ten-ways-to-check-if-an-integer-is-a-power-of-two-in-c/) для обоих случаев ответ начинается с 0, а переменное число равно 0 с / 1 с. Как это определяет, является ли число степенью 2?

Answer 1

Вам нужно обновить себя, как работает бинарный файл. 5 не представлен как 0001 1111 (5 бит включены), он представлен как 0000 0101 (2 ^ 2 + 2 ^ 0), а 4 также не 0000 1111 (4 бита включены), а скорее 0000 0100 (2 ^ 2). Числа, которые вы написали, на самом деле унарные .

В Википедии, как обычно, довольно подробный обзор.

Answer 2

Любая степень двух чисел может быть представлена ​​в двоичном виде с одним 1 и несколькими 0.

eg. 
10000(16) 
1000(8) 
100(4)

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

10000(16) - 1 = 01111(15)

И эти два числа будут давать вам 0 каждый раз.

В случае не-числа из двух чисел вычитание одного оставит по крайней мере одну "1" неизменной где-то в числе как:

10010(18) - 1 = 10001(17)

И эти два приведут к

10000(16) != 0

Answer 3

Имейте в виду, что если x является степенью 2, для устанавливается ровно 1 бит . Вычтите 1, и вы узнаете две вещи: результирующее значение не является степенью двойки, и установленный бит больше не устанавливается. Таким образом, когда вы делаете побитовые и &, каждый бит, который был установлен в x, не сбрасывается, и все биты в (x-1), которые установлены, должны сопоставляться с битами, не установленными в x. Таким образом, каждый бит всегда равен 0.

Другими словами, для любой битовой комбинации вам гарантируется, что (x&(x-1)) равен нулю.

Answer 4

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

Проверяет, является ли значение «n» степенью 2.

Пример:

 if n = 8, the bit representation is 1000
 n & (n-1) = (1000) & ( 0111) = (0000)
 So it return zero only if its value is in power of 2.
 The only exception to this is ‘0’.
 0 & (0-1) = 0 but ‘0’ is not the power of two. 

Почему это имеет смысл?

Представьте, что происходит, когда вы вычитаете 1 из строки битов. Вы читаете слева направо, поворачивая каждый 0 на 1, пока не достигнешь 1, в этот момент этот бит переворачивается:

1000100100 -> (вычесть 1) -> 1000100011

Таким образом, каждый бит, вплоть до первой 1, переворачивается. Если в номере ровно одна единица, то каждый бит (кроме начальных нулей) будет перевернут. Таким образом, n & (n-1) == 0, если есть ровно один 1. Если есть ровно один 1, то это должно быть степень двух.