这个按位运算如何检查2的幂？

Question

我正在看一些应该是微不足道的代码 - 但我的数学在这里惨遭失败.

这是一个条件,使用以下内容检查数字是否为2的幂:

if((num != 1) && (num & (num - 1))) { /* make num pow of 2 */ }

我的问题是,如何在num和num-1之间使用按位AND来确定数字是2的幂？

Answer 1

任何2减1的幂都是1 :( 2 ^N - 1 = 111 .... b )

2 = 2^1.  2-1 = 1 (1b)
4 = 2^2.  4-1 = 3 (11b)
8 = 2^3.  8-1 = 7 (111b)

以8为例.1000&0111 = 0000

因此表达式测试数字是否不是2的幂.

Answer 2

那么,第一种情况将检查2 ⁰ == 1.

对于其他情况,num & (num - 1)它发挥作用:

这就是说,如果你拿任何数字,并从一个较低的位掩盖掉,你会得到两种情况之一:

1. 如果该数字已经是2的幂,则少一个将导致仅设置了低阶位的二进制数.使用&那里什么都不做.

   • 例8:0100 & (0100 - 1)- > (0100 & 0011)- >0000

2. 如果数字不是2的幂,则少一个不会触及最高位,因此结果至少是2的最大幂,小于num.

   • 示例3:0011 & (0011 - 1)- > (0011 & 0010)- >0010

   • 例13:1101 & (1101 - 1)- > (1101 & 1100)- >1100

所以实际的表达式找到的不是2的幂,包括2 ⁰.

Answer 3

我更喜欢这种依赖于补码的方法：

bool checkPowTwo(int x){
    return (x & -x) == x;
}

Answer 4

好,

如果你有X = 1000则x-1 = 0111.而1000 && 0111是0000.

作为2的幂的每个数X具有x-1,其在x位置具有零.按位且0和1始终为0.

如果数字x不是2的幂,例如0110.x-1是0101,并且给出0100.

对于0000 - 1111内的所有组合,这导致

   X  X-1 X && X-1  
0000 1111 0000   
0001 0000 0000 
0010 0001 0000
0011 0010 0010
0100 0011 0000
0101 0100 0100
0110 0101 0100
0111 0110 0110
1000 0111 0000
1001 1000 1000
1010 1001 1000
1011 1010 1010
1100 1011 1000
1101 1100 1100
1110 1101 1100
1111 1110 1110

并且不需要单独检查1.