n & (n-1) 这个表达式是做什么用的？

Question

可能的重复问题:
询问如何判断一个数字是否是2的幂次方
这个函数是做什么用的？

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

- Vishwanath Dalvi

---

请查看此问题：https://dev59.com/S3A75IYBdhLWcg3wfpKr#3265978 - Vladimir

@Paul R，对我来说这不是重复的（尽管相关）-可以说这个问题正好相反。 - Péter Török

它将n的二进制模式中最右边的1变为0。如果结果等于0，则表示n的二进制模式中只有一个1，这意味着n是2的幂。 - shellbye

Answer 1

它的作用是判断n是否为0或2的幂。

这个算法的原理是：二进制表示的2的幂形式为1000...000，减1后得到111...111。当你对这两个数进行按位与（AND）操作时，结果为0，例如：

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

任何非2的幂次方（零以外）作为操作数都不会得到零。

例如，让我们尝试所有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。

- paxdiablo

---

为什么7和-1都有0111？ - sofs1

n & (n-1) 可以帮助我们确定最后一位的值。因为 n 和 n-1 的最低有效位要么是 (0 和 1)，要么是 (1 和 0)。请参考上表。(n & (n-1)) == 0 只检查 n 是否是 2 的幂或者为 0。 - sofs1

这是来自LeetCode的问题。 - Jerry An

Answer 2

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

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

- Paul R

Answer 3

它会检查n是否为2的幂次方：位运算代码“$n & ($n - 1)”是什么意思？

- sarnold

Answer 4

这是一个数字与其前一个数字之间的位运算。只有当n是2的幂时，这个表达式才可能为假，因此实质上你正在验证它是否不是2的幂。

- Neil