n&(n-1)这个表达式做了什么?
可能重复:
查询是否数字是2的幂
这个function有什么作用?
n & (n-1)
– 这个表达式可以用在哪里?
它计算出n
是0还是2的精确幂。
它的工作原理是因为2的二进制幂是1000...000
的forms,减1会产生111...111
。 然后,当你和那些在一起时,你会得到零,例如:
1000 0000 0000 0000 & 111 1111 1111 1111 ==== ==== ==== ==== = 0000 0000 0000 0000
执行该操作时,任何非二次幂输入值(零除外)都不会为零。
例如,让我们尝试所有的4位组合:
<----- binary ----> nn 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
和2的幂( 4
和8
)导致0000/false
位模式,所有其他都是非零或true
。
如果n是2的幂,则返回0(NB:仅适用于n > 0
)。 所以你可以像这样测试2的幂:
bool isPowerOfTwo(int n) { return (n > 0) && ((n & (n - 1)) == 0); }
它检查n是2的幂: 按位代码“$ n&($ n – 1)”是做什么的?
它是一个数字与之前的数字之间的按位运算。 唯一的方法是这个表达式可能是假的,如果n是2的幂,那么基本上你要validation它是否不是2的幂。