java - 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 位模式。