2配方的力量帮助

Question

我知道Java中的(2*i ==(i ^(i - 1)+ 1)会让我发现一个数字是否是2的幂.但有人可以解释为什么这有效吗？

Answer 1

2*i ==(i ^(i-1))+ 1

基本上,如果i是2的幂,它1的位模式就会有一个.如果从中减去1,则该位的所有低位1变为1,并且2位幂将变为0.然后XOR对位进行操作,这将产生全1位模式.你加1,你获得2的下一个幂.

记住异或真值表:

1 ^ 1 = 0
1 ^ 0 = 1
0 ^ 1 = 1
0 ^ 0 = 0

例:

假设i是256,这是这种位模式.

100000000 = 2^8 = 256

100000000 - 1 = 011111111 = 2^7 + 2^6 + ... + 2^0 = 255

100000000 ^ 011111111 = 111111111 = = 2^8 + 2^7 + ... + 2^0 = 511

111111111 + 1 = 1000000000 = 2^9 = 512 = 2*i

这是一个例子,当你没有2的幂

i = 100 = 2^6 + 2^5 + 2^2

0110 0100

0110 0100 - 1 = 99 = 2^6 + 2^5 + 2^1 + 2^0 = 0110 0011

0110 0100 ^ 0110 0011 = 0000 0111 = 2^2 + 2^1 + 2^0 = 7

0000 0111 + 1 = 000 1000 = 2^3 = 8 != (2*i)

简化版

此外,还有此检查的修改版本,以确定某个正无符号整数是否为2的幂.

(i & (i-1)) == 0

基本上,同样的理由

如果i是2的幂,则1其位表示中具有单个位.如果从中减去1,则该1位变为0,并且所有低位变为1.然后AND将产生一个全0位模式.