A linha 294 da fonte java.util.Random diz
if ((n & -n) == n) // i.e., n is a power of 2
// rest of the code
Por que é isso?
java
logic
bit-manipulation
David Weng
fonte
fonte
(n & (n - 1)) == 0também funciona (remove o bit de ordem inferior; se não houver bits restantes, então havia no máximo 1 bit definido em primeiro lugar).Respostas:
A descrição não é totalmente precisa porque
(0 & -0) == 00 não é uma potência de dois. A melhor maneira de dizer é((n & -n) == n)quando n é uma potência de dois, ou o negativo de uma potência de dois, ou zero.Se n for uma potência de dois, então n em binário é um único 1 seguido por zeros. -n no complemento de dois é o inverso + 1, então os bits se alinham assim
n 0000100...000 -n 1111100...000 n & -n 0000100...000Para ver por que este trabalho, considere o complemento de dois como inverso + 1,
-n == ~n + 1n 0000100...000 inverse n 1111011...111 + 1 two's comp 1111100...000já que você carrega um até o fim ao adicionar um para obter o complemento de dois.
Se n fosse qualquer coisa diferente de uma potência de dois †, o resultado estaria perdendo um bit porque o complemento de dois não teria o conjunto de bits mais alto devido a esse transporte.
† - ou zero ou um negativo de uma potência de dois ... conforme explicado no topo.
fonte
(0 & -0) == 0, a declaração imediatamente anterior éif (n <= 0) throw .... O que significa que o número em teste nunca será 0 (ou negativo) nesse ponto.Random.javaque não li.né; Não verifiquei essa suposição, mas de alguma forma duvido que adoublese comportaria da mesma maneira.numa vez que esta questão tem a tag "java".&não está definido emdoubleoufloatem Java. É definido apenas em tipos inteiros e booleanos. Como-não está definido para booleanos, podemos inferir com segurança quené integral.Porque no complemento de 2,
-né~n+1.Se
nfor uma potência de 2, então ele terá apenas um bit definido. Assim~n, todos os bits foram definidos, exceto aquele. Adicione 1 e você definirá o bit especial novamente, garantindo quen & (that thing)seja igual an.O inverso também é verdadeiro porque 0 e números negativos foram descartados pela linha anterior nessa origem Java. Se
ntiver mais de um bit definido, então um deles é o bit mais alto. Este bit não será definido pelo+1porque há um bit claro inferior para "absorvê-lo":n: 00001001000 ~n: 11110110111 -n: 11110111000 // the first 0 bit "absorbed" the +1 ^ | (n & -n) fails to equal n at this bit.fonte
Você precisa olhar os valores como bitmaps para ver por que isso é verdade:
1 & 1 = 1 1 & 0 = 0 0 & 1 = 0 0 & 0 = 0Portanto, apenas se os dois campos forem 1, um 1 será exibido.
Agora -n faz um complemento de 2. Muda tudo
0para1e adiciona 1.7 = 00000111 -1 = NEG(7) + 1 = 11111000 + 1 = 11111001Contudo
8 = 00001000 -8 = 11110111 + 1 = 11111000 00001000 (8) 11111000 (-8) --------- & 00001000 = 8.Apenas para potências de 2 será
(n & -n)n.Isso ocorre porque uma potência de 2 é representada como um único bit definido em um longo mar de zeros. A negação produzirá exatamente o oposto, um único zero (no local onde o 1 costumava ser) em um mar de 1's. Adicionar 1 deslocará os inferiores para o espaço onde está o zero.
E o bit a bit e (&) filtrará o 1 novamente.
fonte
Na representação de complemento de dois, a única coisa sobre potências de dois, é que eles consistem em todos os bits 0, exceto para o k-ésimo bit, onde n = 2 ^ k:
base 2 base 10 000001 = 1 000010 = 2 000100 = 4 ...Para obter um valor negativo no complemento de dois, você inverte todos os bits e adiciona um. Para potências de dois, isso significa que você obtém um monte de 1s à esquerda até e incluindo o bit 1 que estava no valor positivo e, em seguida, um monte de 0s à direita:
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 001000Você pode ver facilmente que o resultado das colunas 2 e 4 será o mesmo da coluna 2.
Se você observar os outros valores ausentes neste gráfico, poderá ver por que isso não vale para nada além das potências de dois:
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 terá (para n> 0) apenas 1 bit definido, e esse bit será o bit menos significativo definido em n. Para todos os números com potências de dois, o bit definido menos significativo é o único bit definido. Para todos os outros números, há mais de um conjunto de bits, dos quais apenas o menos significativo será definido no resultado.
fonte
É propriedade das potências de 2 e do complemento de dois .
Por exemplo, pegue 8:
8 = 0b00001000 -8 = 0b11111000Calculando o complemento de dois:
Starting: 0b00001000 Flip bits: 0b11110111 (one's complement) Add one: 0b11111000 AND 8 : 0b00001000Para potências de 2, apenas um bit será definido, portanto, a adição fará com que o enésimo bit de 2 n seja definido (aquele continua carregando para o enésimo bit). Então, quando você
ANDos dois números, obtém o original de volta.Para números que não são potências de 2, os outros bits não serão invertidos, portanto, o
ANDnão produz o número original.fonte
Simplesmente, se n é uma potência de 2, isso significa que apenas um bit é definido como 1 e os outros são 0s:
00000...00001 = 2 ^ 0 00000...00010 = 2 ^ 1 00000...00100 = 2 ^ 2 00000...01000 = 2 ^ 3 00000...10000 = 2 ^ 4 and so on ...e porque
-né um complemento de 2 den(isso significa que o único bit que é 1 permanece como está e os bits do lado esquerdo desse bit são colocados em 1, o que na verdade não importa visto que o resultado do operador AND&será 0 se um dos dois bits é zero):000000...000010000...00000 <<< n & 111111...111110000...00000 <<< -n -------------------------- 000000...000010000...00000 <<< nfonte
Mostrado por exemplo:
8 em hexadecimal = 0x000008
-8 em hex = 0xFFFFF8
8 e -8 = 0x000008
fonte