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的位模式。您将其加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位模式。