我知道 Java 中的 (2 * i == (i ^( i - 1) + 1) 可以让我找到一个数字是否是 2 的幂。但是有人可以解释为什么这样做吗？
2*i==(i^(i-1))+1
基本上，如果i是 2 的幂，它将有一个1在其位模式中。如果从中减去 1，则该值的所有低位1有点变成1，并且该两位的幂将变为 0。然后您执行XOR位上，这会产生全 1 位模式。再加上 1，就得到了 2 的下一个幂。
记住异或真值表：
1 ^ 1 = 0
1 ^ 0 = 1
0 ^ 1 = 1
0 ^ 0 = 0
Example:
比方说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
基本道理是一样的
If i是 2 的幂，它有一个1位在其位表示中。如果从中减去 1，则1位变为 0，所有低位变为1. Then AND将产生一个全部0位模式。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
