“整数是否为2次幂的算法”的版本间的差异

来自姬鸿昌的知识库
跳到导航 跳到搜索
 
（未显示同一用户的3个中间版本）
第1行： 第1行：
−
https://www.bilibili.com/video/BV1kA411u7xD/
+
https://www.bilibili.com/video/BV1kA411u7xD
  
 
<syntaxhighlight lang="c">
 
<syntaxhighlight lang="c">
第37行： 第37行：
 
|
 
|
 
|1
 
|1
 +
|0
 +
|……
 
|0
 
|0
 
|0
 
|0
第43行： 第45行：
 
|0
 
|0
 
|1
 
|1
 +
|省略号
 
|1
 
|1
 +
|1
 +
|-
 +
|=
 +
|0
 +
|0
 +
|……
 +
|0
 +
|0
 +
|}
 +
如果是 n=1，那么就是：
 +
{| class="wikitable"
 +
|
 +
|0
 +
|0
 +
|1
 +
|-
 +
|&
 +
|0
 +
|0
 +
|0
 
|-
 
|-
 
|=
 
|=
第50行： 第73行：
 
|0
 
|0
 
|}
 
|}
 +
复杂度O(n)

2022年11月6日 (日) 21:45的最新版本

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)

取自“https://www.jihongchang.top/index.php?title=整数是否为2次幂的算法&oldid=3334”