整数是否为2次幂的算法
跳到导航
跳到搜索
https://www.bilibili.com/video/BV1kA411u7xD
int pow2(int n)
{
return (n > 0) && ((n & (n - 1)) == 0);
}
int main()
{
int a = 31;
int ret = pow2(a);
printf("ret = %d \n", ret);
return 0;
}
注意：
“==”（等于运算符）要比“&”按位与运算符优先级高，所以“n&(n-1)”要先套一层括号再进行“==0”的判断。
算法原理：
20=1 (1)2
21=2 (10)2
22=4 (100)2
23=8 (1000)2
24=16 (10000)2
……
n（任意整数）不是奇数就是偶数，和 n-1 进行按位与运算就是：
| 1 | 0 | …… | 0 | 0 | |
| & | 0 | 1 | 省略号 | 1 | 1 |
| = | 0 | 0 | …… | 0 | 0 |
如果是 n=1，那么就是：
| 0 | 0 | 1 | |
| & | 0 | 0 | 0 |
| = | 0 | 0 | 0 |
复杂度O(n)