如何从数学上证明‘i & (i - 1) == 0’等价于正整数i是2的幂？

先明确两个前置规则：

• 正整数的二进制表示：任何正整数都能写成二进制形式，每一位对应2的幂次，1代表该幂次被包含，0代表不包含。
• 按位与（&）运算规则：只有当两个数的对应二进制位同时为1时，结果的该位才是1，其余情况为0。

充分性证明（若i & (i - 1) == 0，则i是2的幂） #

用反证法推导：
假设存在正整数i，满足i & (i - 1) == 0，但i不是2的幂。

因为i不是2的幂，它的二进制表示里至少有两个1（2的幂的二进制只有最高位是1，其余全为0）。比如i的二进制是...1x...1（x代表任意数量的0或1，至少有两个1）。

当计算i-1时，二进制会发生这样的变化：从最右边的1开始，把这个1翻转为0，同时它右边所有的0都翻转为1。比如i是1010（十进制10），i-1就是1001。

由于i的二进制里至少有两个1，最右边的1被翻转后，它左边的那个1不会被减1操作影响，仍然是1。这时候i和i-1的二进制中，左边的这个1的位置上，两者都是1，按位与的结果在该位就是1——也就是说i & (i - 1)的结果至少有一位是1，不可能等于0。

这和我们的假设i & (i - 1) == 0矛盾，因此假设不成立。结论：满足i & (i - 1) == 0的正整数i一定是2的幂。

补充：必要性验证（若i是2的幂，则i & (i - 1) == 0） #

如果i是2的幂，它的二进制是100...0（只有最高位为1），那么i-1的二进制就是011...1（最高位为0，其余全为1）。两者按位与时，每一位都没有同时为1的情况，结果必然是0，这部分很好理解。

内容的提问来源于stack exchange，提问作者ripfreeworld