Строка 294 источника java.util.Random говорит
if ((n & -n) == n) // i.e., n is a power of 2
// rest of the code
Почему это?
java
logic
bit-manipulation
Дэвид Венг
источник
источник
(n & (n - 1)) == 0также работает (она удаляет бит самого низкого порядка, если битов не осталось, значит, изначально был установлен не более 1 бит).Ответы:
Описание не совсем точное, потому что
(0 & -0) == 00 - это не степень двойки. Лучший способ сказать это((n & -n) == n)когда n является степенью двойки, или отрицательной величиной степени двойки, или нулем.Если n является степенью двойки, то n в двоичном формате представляет собой единицу с нулями. -n в дополнении до двух - это инверсия + 1, поэтому биты выстраиваются таким образом
n 0000100...000 -n 1111100...000 n & -n 0000100...000Чтобы понять, почему это работает, рассмотрим дополнение до двух как обратное + 1,
-n == ~n + 1n 0000100...000 inverse n 1111011...111 + 1 two's comp 1111100...000так как вы проводите один полностью, добавляя один, чтобы получить два дополнения.
Если бы n было чем-то другим, кроме степени двойки †, тогда в результате был бы пропущен бит, потому что в дополнительном двоичном коде не был бы установлен самый высокий бит из-за этого переноса.
† - или ноль, или отрицательное значение степени двойки ... как объяснено вверху.
источник
(0 & -0) == 0, непосредственно предшествующего заявления являетсяif (n <= 0) throw .... Это означает, что в этот момент тестируемое число никогда не будет 0 (или отрицательным).Random.javaкоторый я не читал.n; Я не проверял это предположение, но почему-то сомневаюсь, что adoubleбудет вести себя так же.nпоскольку в этом вопросе есть тег "java".&не определен на Javadoubleилиfloatв Java. Он определен только для целочисленных типов и логических значений. Поскольку-не определено для логических значений, мы можем с уверенностью сделать вывод, чтоnявляется целым.Поскольку в дополнении до 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.источник
Чтобы понять, почему это так, вам нужно рассматривать значения как растровые изображения:
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.
источник
В представлении дополнения до двух уникальность степеней двойки состоит в том, что они состоят из всех 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 001000n & -n (для n> 0) будет иметь только 1 установленный бит, и этот бит будет наименее значимым установленным битом в n. Для всех чисел, являющихся степенями двойки, единственный установленный бит является младшим значащим битом. Для всех других чисел существует более одного набора битов, из которых в результате будет установлен только наименее значимый.
источник
Это свойство степеней двойки и их дополнения до двух. .
Например, возьмите 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исходное число не будет возвращено .источник
Проще говоря, если 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это дополнение до 2n(это означает, что единственный бит, который равен 1, остается таким, как есть, а биты с левой стороны этого бита сидят на 1, что на самом деле не имеет значения, поскольку результат оператора AND&будет 0, если один из двух бит равен нулю):000000...000010000...00000 <<< n & 111111...111110000...00000 <<< -n -------------------------- 000000...000010000...00000 <<< nисточник
Показано на примере:
8 в шестнадцатеричном формате = 0x000008
-8 в шестнадцатеричном формате = 0xFFFFF8
8 & -8 = 0x000008
источник