C语言 n & (n-1) 这个表达式有什么作用？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/4678333/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
n & (n-1) what does this expression do?
提问by mr_eclair
Possible Duplicates:
Query about working out whether number is a power of 2
What does this function do?
可能的重复项：
查询数字是否是 2 的幂
这个函数有什么作用？
n & (n-1)- where can this expression be used ?
n & (n-1)- 这个表达式可以用在哪里？
回答by paxdiablo
It's figuring out if nis either 0 or an exact power of two.
它正在确定n是 0 还是 2 的精确幂。
It works because a binary power of two is of the form 1000...000and subtracting one will give you 111...111. Then, when you AND those together, you get zero, such as with:
它的工作原理是二的二进制幂的形式1000...000，减一会给你111...111。然后，当你把它们加在一起时，你会得到零，例如：
1000 0000 0000 0000
& 111 1111 1111 1111
==== ==== ==== ====
= 0000 0000 0000 0000
Any non-power-of-two input value (other than zero) will notgive you zero when you perform that operation.
当您执行该操作时，任何非 2 的幂输入值（零除外）都不会为您提供零。
For example, let's try all the 4-bit combinations:
例如，让我们尝试所有 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
You can see that only 0and the powers of two (1, 2, 4and 8) result in a 0000/falsebit pattern, all others are non-zero or true.
您可以看到，只有0和 两个 ( 1, 2,4和8)的幂导致0000/false位模式，所有其他的都是非零或true。
回答by Paul R
It returns 0 if n is a power of 2 (NB: only works for n > 0). So you can test for a power of 2 like this:
如果 n 是 2 的幂，则返回 0（注意：仅适用于n > 0）。所以你可以像这样测试 2 的幂：
bool isPowerOfTwo(int n)
{
return (n > 0) && ((n & (n - 1)) == 0);
}
回答by sarnold
It checks if n is a power of 2: What does the bitwise code "$n & ($n - 1)" do?
它检查 n 是否是 2 的幂：按位代码 "$n & ($n - 1)" 有什么作用？
回答by Neil
It's a bitwise operation between a number and its previous number. Only way this expression could ever be false is if n is a power of 2, so essentially you're verifying if it isn't a power of 2.
这是一个数字与其前一个数字之间的按位运算。只有当 n 是 2 的幂时，这个表达式才会为假，所以本质上你是在验证它是否不是 2 的幂。
