n&(n-1)这个表达式做了什么？

Question

可能重复:
询问是否数字是2的幂是
什么？这个功能有什么作用？

n & (n-1) - 这个表达式可以在哪里使用？

Answer 1

它计算出n是0还是2的精确幂.

它的工作原理是因为二进制幂的形式1000...000和减去一个会给你111...111.然后,当你和那些在一起时,你会得到零,例如:

  1000 0000 0000 0000
&  111 1111 1111 1111
  ==== ==== ==== ====
= 0000 0000 0000 0000

执行该操作时,任何非二次幂输入值(零除外)都不会为零.

例如,让我们尝试所有的4位组合:

     <----- binary ---->
 n      n    n-1   n&(n-1)
--   ----   ----   -------
 0   0000   0111    0000 *
 1   0001   0000    0000 *
 2   0010   0001    0000 *
 3   0011   0010    0010
 4   0100   0011    0000 *
 5   0101   0100    0100
 6   0110   0101    0100
 7   0111   0110    0110
 8   1000   0111    0000 *
 9   1001   1000    1000
10   1010   1001    1000
11   1011   1010    1010
12   1100   1011    1000
13   1101   1100    1100
14   1110   1101    1100
15   1111   1110    1110

你可以看到,只有0和两个(权力1,2,4和8)导致0000/false的位模式,其他均为非零和true.

Answer 2

如果 n 是 2 的幂，则返回 0（注意：仅适用于n > 0）。因此，您可以像这样测试 2 的幂：

bool isPowerOfTwo(int n)
{
    return (n > 0) && ((n & (n - 1)) == 0);
}