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

Ответ 1

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

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

Если n является степенью двух, то n в двоичном выражении является единственным 1, за которым следуют нули. -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 comp 1111100...000

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

Если n было чем-то иным, чем силой двух кинжалов; то результат будет отсутствовать, потому что у двух дополнителей не будет установлен самый старший бит из-за переноса.

& крестик; - или ноль или отрицательный от мощности двух... как объяснено в верхней части.

Ответ 2

Потому что в 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.

Ответ 3

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

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

Итак, только если оба поля равны 1, выдается 1.

Теперь - имеет 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) be n.
Это связано с тем, что мощность 2 представлена ​​как единый бит в длинном море нулей. Отрицание даст полную противоположность, один ноль (в месте, где раньше было 1) в море 1-го. Добавление 1 приведет к сдвигу нижних в пространство, где находится нуль.
И Побитовое и (&) снова отфильтровывают 1.

Ответ 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. Для всех чисел, которые являются степенями двух, наименее значимый бит набора является единственным установленным битом. Для всех других чисел существует более одного битового набора, из которого в результате будет задано только наименьшее значение.

Ответ 5

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

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

8  = 0b00001000

-8 = 0b11111000

Вычисление двух дополнений:

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

AND 8    : 0b00001000

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

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

Ответ 6

Просто, если 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

Ответ 7

Пример:

8 в hex = 0x000008

-8 в hex = 0xFFFFF8

8 и -8 = 0x000008