Почему, если (n & -n) == n, то n является степенью 2?

Question

Строка 294 java.util.Случайный источник говорит

if ((n & -n) == n) // i.e., n is a power of 2
    // rest of the code

Почему это?

Answer 1

Поскольку в дополнении 2 -n равно ~n+1.

Если n - это степень 2, то для него установлен только один бит.Итак, ~n имеет все установленные биты, кроме этого.Добавьте 1, и вы снова установите специальный бит, гарантируя, что n & (that thing) равен n.

Обратное также верно, потому что 0 и отрицательные числа были исключены предыдущей строкой в ​​этом источнике Java,Если n имеет более одного установленного бита, то один из них является старшим таким битом.Этот бит не будет установлен +1, потому что есть нижний бит сброса, чтобы «поглотить» его:

 n: 00001001000
~n: 11110110111
-n: 11110111000  // the first 0 bit "absorbed" the +1
        ^
        |
        (n & -n) fails to equal n at this bit.

Answer 2

Описание не совсем точное, потому что (0 & -0) == 0, но 0 не является степенью двойки.Лучший способ сказать, что это

((n & -n) == n), когда n - это степень двойки, или отрицательная степень, равная двум, или ноль.

Если n - это степень двойки,тогда n в двоичном коде - это единица, за которой следуют нули.-n в дополнении к двоичному является обратным + 1, поэтому биты выстраиваются в линию таким образом

 n      0000100...000
-n      1111100...000
 n & -n 0000100...000

Чтобы понять, почему эта работа, рассмотрим дополнение к двум как обратное + 1, -n == ~n + 1

n          0000100...000
inverse n  1111011...111
                     + 1
two's comp 1111100...000

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

Если бы n было чем-то отличным от степени двойки †, результат был бы немного пропущен, потому что дополнение к двум не будетустановить максимальный бит из-за этого переноса.

† - или ноль или минус степени двойки ... как объяснено сверху.

Answer 3

Вам нужно посмотреть на значения как растровые изображения, чтобы понять, почему это так:

1 & 1 = 1
1 & 0 = 0
0 & 1 = 0
0 & 0 = 0

Таким образом, только если оба поля равны 1, появится 1.

Теперь -n делает дополнение 2. Он изменяет все значения 0 на 1 и добавляет 1.

7 = 00000111
-1 = NEG(7) + 1 = 11111000 + 1 = 11111001

Тем не менее

8 = 00001000
-8 = 11110111 + 1 = 11111000 

00001000  (8)
11111000  (-8)
--------- &
00001000 = 8.

Только для степеней 2 (n & -n) будет n.
Это связано с тем, что степень 2 представляется в виде единого установленного бита в длинном море нулей. Отрицание приведет к полной противоположности: один ноль (в месте, где раньше была 1) в море единиц. Добавление 1 сместит нижние в пространство, где находится ноль.
И побитовые и (&) снова отфильтруют 1.

Answer 4

В представлении дополнения к двум уникальным свойством двух степеней является то, что они состоят из всех 0 битов, кроме k-го бита, где n = 2 ^ k:

base 2    base 10
000001 =  1 
000010 =  2
000100 =  4
     ...

Чтобы получить отрицательное значение в дополнении до двух, вы переворачиваете все биты и добавляете один. Для степеней двойки это означает, что вы получаете группу 1 с слева до включающего 1 бита, который был в положительном значении, а затем группу 0 с справа:

n   base 2  ~n      ~n+1 (-n)   n&-n  
1   000001  111110  111111      000001
2   000010  111101  111110      000010
4   000100  111011  111100      000100
8   001000  110111  111000      001000

Вы можете легко увидеть, что результат столбцов 2 и 4 будет таким же, как столбец 2.

Если вы посмотрите на другие значения, отсутствующие на этом графике, вы поймете, почему это не относится ни к чему, кроме степеней двух:

n   base 2  ~n      ~n+1 (-n)   n&-n  
1   000001  111110  111111      000001
2   000010  111101  111110      000010
3   000011  111100  111101      000001
4   000100  111011  111100      000100
5   000101  111010  111011      000001
6   000110  111001  111010      000010
7   000111  111000  111001      000001
8   001000  110111  111000      001000

n & -n будет (для n> 0) иметь только 1 установленный бит, и этот бит будет самым младшим установленным битом в n. Для всех чисел, имеющих степени двойки, младший значащий установленный бит является единственным установленным битом. Для всех остальных чисел задано более одного бита, из которых в результате будет задано только наименее значимое.

Answer 5

Проще говоря, если n - это степень 2, это означает, что только один бит установлен в 1, а остальные равны 0:

00000...00001 = 2 ^ 0
00000...00010 = 2 ^ 1
00000...00100 = 2 ^ 2
00000...01000 = 2 ^ 3
00000...10000 = 2 ^ 4

and so on ...

, а поскольку -n является дополнением 2 к n (это означает, что единственный бит, который равен 1, остается таким, как есть, и биты на левой стороне этого бита установлены в 1, что на самом деле не имеет значения, так как результат оператора И & будет равен 0, если один из двух битовноль):

000000...000010000...00000 <<< n
&
111111...111110000...00000 <<< -n
--------------------------
000000...000010000...00000 <<< n

Answer 6

Это свойство степеней 2 и их дополнения до двух .

Например, взять 8:

8  = 0b00001000

-8 = 0b11111000

Расчет дополнения до двух:

Starting:  0b00001000
Flip bits: 0b11110111  (one's complement)
Add one:   0b11111000  

AND 8    : 0b00001000

Для степеней 2 будет установлен только один бит , поэтому добавление приведет к установке n ^th бита 2 ⁿ перенос на n ^th бит). Затем, когда вы AND наберете два числа, вы получите оригинал обратно.

Для чисел, не являющихся степенями 2, другие биты не будут перевернуты, поэтому AND не даст исходное число.

Answer 7

В примере показано:

8 в шестнадцатеричном виде = 0x000008

-8 в шестнадцатеричном = 0xFFFFF8

8 & -8 = 0x000008