Как «&» работает для цифрового сравнения?

Question

def power_of_two?(n) 
    n & (n-1) == 0 
end 

Этот метод проверяет, является ли данный номер n мощностью двух. Как это работает? Я не понимаю, как используется &

Answer 1

& называется оператором побитового И.

The AND operator Просматривает двоичное представление двух поставленных целых чисел по биту. Если биты в том же самом положении в обоих чисел равны 1 в результате целое число, будут иметь этот бит установлен в 1. Если нет, то бит будет установлен в 0:

(a = 18).to_s(2)  #=> "10010" 
(b = 20).to_s(2)  #=> "10100" 
(a & b).to_s(2)  #=> "10000" 

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

• Пример с 8: 0100 & (0100 - 1) ->(0100 & 0011) ->0000

Чтобы понять это следовать "How does this bitwise operation check for a power of 2?".

Пример через IRB:

>> 4.to_s(2) 
=> "100" 
>> 3.to_s(2) 
=> "11" 
>> 4 & 3 
=> 0 
>> 

Вот почему вы можете сказать 4 является мощность 2 числа.

Answer 2

«&» является поразным «И» (см. http://calleerlandsson.com/2014/02/06/rubys-bitwise-operators/). Он сравнивает два числа, как описано в следующем примере:

Предположим, что n = 4 (что равно двум). Это означает, что n-1 = 3. В двоичном формате (который я пишу с одними и нулями в кавычках типа «1101011101», поэтому мы можем видеть биты), мы имеем n = «100» и n-1 = «011».

В побитовом И из этих двух чисел 0 = «000» (в дальнейшем, каждый столбец содержит только один 1, никогда не два 1s)

100   <-- this is n, n=4 
011   <-- this is n-1, n-1=3 
--- 
000   <-- this is n & (n-1) 

В качестве другого примера, в настоящее время позволяет сказать что n = 14 (не мощность двух), и поэтому n-1 = 13. В этом случае п = «1110» и п-1 = «1101», и мы имеем п & (п-1) = 12

1110   <-- this is n, n=14 
1101   <-- this is n-1, n-1=13 
---- 
1100   <-- this is n & (n-1) 

В приведенном выше примере, первые две колонки п и п- 1 оба содержат 1, таким образом, И этих столбцов является одним.

Хорошо, рассмотрим один из последних примеров, когда n снова является степенью двух (это должно сделать его достаточно понятным, если это еще не так, почему «poweroftwo?» Записывается так, как есть. Предположим, что n = 16 (что является мощность двух)

Предположим, что n = 16 (что равно двум). Это означает, что n-1 = 15, поэтому мы имеем n = «10000» и n-1 = «01111».

В побитовом И из этих двух чисел 0 = «00000» (в дальнейшем, каждый столбец содержит только один 1, никогда не два 1s)

10000   <-- this is n, n=16 
01111   <-- this is n-1, n-1=15 
--- 
00000   <-- this is n & (n-1) 

Caveat: В особом случае, n = 0, функция "power_of_two?" вернет True, хотя n = 0 не является степенью двух. Это связано с тем, что 0 представляется как битовая строка всех нулей, а все ANDED с нулем равно нулю.

Итак, в общем, функция «power_of_two?» вернет True тогда и только тогда, когда n является степенью двух или n равно нулю. Вышеприведенные примеры только иллюстрируют этот факт, они не доказывают это ... Однако это так.

Answer 3

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

0b1000 & (0b1000 - 1) = 0b1000 & 0b111 = 0

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

С другой стороны, если число не равно двум, результат должен быть отличным от нуля.

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

Answer 4

Процедура уменьшения одной из двоичного числа, начиная с наименьшего значащего бита:

1. если бит равен 0 - превратить его в 1 и перейти к следующему значащего бита
2. если бит - 1 - превратите его в 0 и остановите.

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

Давайте скажем первого1 в нашем номере n находится в положении i. Если мы сместим справа на номер n, мы получим часть номера, которая не изменилась, когда мы уменьшили ее, назовем это m.Если мы перемещаем число n-1 мы должны получить одинаковое количество m, именно потому, что это та часть, которая не изменилась, когда мы уменьшили одно:

n >> i == m 
(n - 1) >> i == m 

Shifting правильные две цифры на ту же сумму будет также сдвиг вправо на ту же сумму в результате & ИНГ их:

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

Но 0 >> i является 0, независимо от i, так:

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

Давайте соберем m, где мы знаем, что это:

m & m == 0 

Но мы также знаем, что:

m & m == m # for any m 

m == 0 Так!

Поэтому n & (n - 1) == 0 в том и только в том случае, если имеется не более 1 бит в числе n.

Единственные цифры, которые имеют более одного 1 бита являются всеми (неотрицательными) полномочиями 2 (ведущим 1 и неотрицательное число нулей после нее), а число 0.

QED

Answer 5

Мы хотим доказать, что

n & (n-1) == 0 

тогда и только тогда, когда n это сила 2.

Мы можем предположить, что n является целым числом более 1. (На самом деле, я буду использовать это предположение, чтобы получить сокращение.)

Если n это сила 2, его бинарное представление имеет 1 в битовые смещения

p = log2(n) 

и 0 с при всех нижне- разрядные позиции заказа j, j < p. Более того, поскольку (n-1)+1 = n, n-1 должно иметь 1 во всех смещениях бит j, 0 <= j < p. Поэтому

n & (n-1) == 0 

Остается доказать, что если n не сила 2 и

n & m == 0 

затем m != n-1. Я предполагаю, что m = n-1 и получит сжатие, тем самым завершая доказательство.

n Наиболее значимый бит - это, конечно, 1.Поскольку n не имеет силы 2, n имеет хотя бы один другой бит, равный 1. Среди этих 1-битов рассмотрим тот, который находится в самом значительном битовом положении j.

С n & (n-1) == 0, n-1 должен иметь 0 в положении j его двоичного представления. Когда мы добавим к 1n-1, чтобы сделать его равным n, он должен иметь 1 со смещением j, а это означает, что n-1 должны 1 «S во всех битовых позициях < j. Кроме того, (n-1)+1 имеет нули во всех положениях битов < j после 1. Но с n = (n-1)+1, это может быть правдой, только если j == 0, начиная с n & (n-1) == 0. Следовательно, для того, чтобы это было правдой, наиболее значимые и наименее значимые биты n, наиболее равные 1, и все остальные биты должны быть равны нулю. Однако, начиная с n = (n-1)+1, это подразумевает n-1==0 и, следовательно, n == 1, необходимое противоречие.

(Уф! Там должен быть проще доказательство!)