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

84

Строка 294 источника java.util.Random говорит

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

Почему это?

Дэвид Венг
источник
2
Новый тег должен быть подсказкой. :)
bzlm
10
Вот ответ: stackoverflow.com/questions/600293/…
Джейкоб Мэттисон,
2
Следите за битами. Между прочим, он также считает ноль как степень двойки. Формула (n & (n - 1)) == 0также работает (она удаляет бит самого низкого порядка, если битов не осталось, значит, изначально был установлен не более 1 бит).
Гарольд
3
Да, я признаю себя виновным в использовании такого кода. Есть ряд подобных уловок, в которые вы можете играть, если вы знаете, что имеете дело с арифметикой с дополнением до 2, и помните о различных ловушках преобразования и переполнения. Для дополнительной выгоды выясните, как округлить до следующей большей степени двойки или, возможно, степени двойки - 1 - то, что нужно делать с удивительной частотой в некоторых случаях.
Hot Licks
1
Подождите, все ли сейчас читают из источника java.util.Random? (Я прочитал это несколько месяцев назад, и с тех пор я помню несколько вопросов об этом на SO.)
Матин Улхак

Ответы:

48

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

((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 было чем-то другим, кроме степени двойки †, тогда в результате был бы пропущен бит, потому что в дополнительном двоичном коде не был бы установлен самый высокий бит из-за этого переноса.

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

Майк Сэмюэл
источник
И есть уловка, чтобы изолировать младший 1 бит.
Hot Licks
2
Что касается (0 & -0) == 0, непосредственно предшествующего заявления является if (n <= 0) throw .... Это означает, что в этот момент тестируемое число никогда не будет 0 (или отрицательным).
пользователь
1
@ Майкл, совершенно верно. Я отвечал на вопрос в заголовке, не критикуя, Random.javaкоторый я не читал.
Майк Сэмюэл,
1
@ Майк, я это понимаю; однако я не думаю, что утверждение в комментарии в коде (которое включено в вопрос и является основанием для вопроса в заголовке) вполне само по себе, если оно не рассматривается в контексте предварительных условий, установленных непосредственно перед к нему в коде. Если вы посмотрите только на вопрос, размещенный здесь, мы даже ничего не знаем о том, что это за тип n; Я не проверял это предположение, но почему-то сомневаюсь, что a doubleбудет вести себя так же.
пользователь
3
@Michael, мы можем поставить довольно хорошие границы для типа, nпоскольку в этом вопросе есть тег "java". &не определен на Java doubleили floatв Java. Он определен только для целочисленных типов и логических значений. Поскольку -не определено для логических значений, мы можем с уверенностью сделать вывод, что nявляется целым.
Майк Сэмюэл
95

Поскольку в дополнении до 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.
Стив Джессоп
источник
13

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

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.

Йохан
источник
8

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

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

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

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

Затмение
источник
4

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

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

8  = 0b00001000

-8 = 0b11111000

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

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

AND 8    : 0b00001000

Для степеней двойки будет установлен только один бит, поэтому добавление приведет к установке n- го бита 2 n (один продолжает переноситься на n- й бит). Тогда, когда тыAND наберете два числа, вы получите оригинал обратно.

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

Остин Салонен
источник
4

Проще говоря, если 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, что на самом деле не имеет значения, поскольку результат оператора AND &будет 0, если один из двух бит равен нулю):

000000...000010000...00000 <<< n
&
111111...111110000...00000 <<< -n
--------------------------
000000...000010000...00000 <<< n
Eng.Fouad
источник
0

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

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

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

8 & -8 = 0x000008

Джон Б.
источник