Использование битовых манипуляций для определения того, можно ли выразить целое число без знака в форме 2 ^ n-1

Question

Чтобы проверить, имеет ли целое число без знака форму 2^n-1, мы используем:

x&(x+1)

Что это должно быть равным? То есть

x&(x+1) == ?

Answer 1

В форме вида 2^n-1 будут установлены все биты до n-го бита. Например, 2^3-1 (7):

0b0111

Если мы добавим один к этому, мы получим 8:

0b1000

Затем, выполняя побитовое и, мы видим, что мы получаем ноль, потому что в обоих числах бит не установлен Если мы начнем с числа, отличного от 2^n+1, результат будет ненулевым.

Answer 2

В дополнение к существующим ответам, вот краткое объяснение того, почему числа x не имеют форму 0b00000 (ноль) или 0b0111..11 (установлены все младшие цифры, это все числа 2 ^n-1 для n> 0) не имеют свойства x&(x+1) == 0.

Для числа x вида 0b????1000..00, x+1 имеет те же цифры, что и x, за исключениеммладший значащий бит, поэтому x & (x+1) имеет хотя бы один установленный бит, бит, который отображался как установленный в x.Для краткого объяснения:

x       0b????1000..00
x+1     0b????1000..01
x&(x+1) 0b????10000000

Для числа x вида 0b????10111..11:

x       0b????10111..11
x+1     0b????110000000
x&(x+1) 0b????10000..00

В заключение, если x не является ни нулем, ни записаннымв двоичном формате со всеми установленными младшими цифрами, тогда x&(x+1) не равно нулю.

Answer 3

ноль.Если X равен 2 ^ N-1, это непрерывная строка из 1 в двоичном виде.Еще одно - это 1, за которым следует строка с нулями такой же длины, что и X, поэтому два числа не имеют общих 1-битов в любом месте, поэтому AND для двух равно нулю.