如何证明“i & (i - 1) == 0”意味着“i是2的幂”

Question

如果我们事先知道

i

一定是类似

10...0

的东西，就不难想象了。
但如何证明

i & (i - 1) == 0

足以证明 i 是 2 的幂（至少对于正整数）？

Answer 1

从技术上讲，该声明不正确，如果

i

是 signed

int

，则应该是

i & i - 1 == 0

当且仅当

i

是

2

或

0

的幂

很简单：

如果

i

是2

的

幂，那么in可以表示为

1000...000

（二进制） 我们有

  1000...000 - i is a power of 2 
  0111...000 - i - 1
  ----------
  0000000000 = 0

如果

i

是

0

那么我们有

          0 i
  111...111 -1 (2 compliment)
  ---------
          0

如果

i

不是2

或

0

的幂，那么它至少有

两个位设置，比如

  i = 1..010...0
          ^- rigtmost 1

我们有

  1..010...0 - i
  1..001...1 - i - 1 
  ----------
  1.. 000000 > 0