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

来自姬鸿昌的知识库
跳到导航 跳到搜索
（建立内容为“https://www.bilibili.com/video/BV1kA411u7xD/”的新页面）
 
 
（未显示同一用户的4个中间版本）
第1行： 第1行：
−
https://www.bilibili.com/video/BV1kA411u7xD/
+
https://www.bilibili.com/video/BV1kA411u7xD
 +
 
 +
<syntaxhighlight lang="c">
 +
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;
 +
}
 +
</syntaxhighlight>注意：
 +
 
 +
“==”（等于运算符）要比“&”按位与运算符优先级高，所以“n&(n-1)”要先套一层括号再进行“==0”的判断。
 +
 
 +
 
 +
算法原理：
 +
 
 +
2<sup>0</sup>=1  (1)<sub>2</sub>
 +
 
 +
2<sup>1</sup>=2  (10)<sub>2</sub>
 +
 
 +
2<sup>2</sup>=4  (100)<sub>2</sub>
 +
 
 +
2<sup>3</sup>=8  (1000)<sub>2</sub>
 +
 
 +
2<sup>4</sup>=16 (10000)<sub>2</sub>
 +
 
 +
……
 +
 
 +
n（任意整数）不是奇数就是偶数，和 n-1 进行按位与运算就是：
 +
{| class="wikitable"
 +
|
 +
|1
 +
|0
 +
|……
 +
|0
 +
|0
 +
|-
 +
|&
 +
|0
 +
|1
 +
|省略号
 +
|1
 +
|1
 +
|-
 +
|=
 +
|0
 +
|0
 +
|……
 +
|0
 +
|0
 +
|}
 +
如果是 n=1，那么就是：
 +
{| class="wikitable"
 +
|
 +
|0
 +
|0
 +
|1
 +
|-
 +
|&
 +
|0
 +
|0
 +
|0
 +
|-
 +
|=
 +
|0
 +
|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”