[算法很美](位运算_4)二进制中1的个数
4、用一条语句判断一个整数是不是2的整数次方
如果我们没有接触过上几道题,我们能否想到用二进制来做呢?当然不太可能吧,我们所想的就只能将给定的n不断除2,每次判断它是否为偶数
int main()
{
int n;
scanf("%d", &n);
if (n == 1) {
printf("No");
return 0;
}
while (n > 1)
{
if (n % 2 == 0)
n /= 2;
else {
printf("No");
return 0;
}
}
printf("yes");
return 0;
}
思路:我们看看2的整数次方有哪些?2,4,8,16,32,我们来看看它们的二进制:
- 0000 0000 0000 0010(2)
- 0000 0000 0000 0100(4)
- 0000 0000 0000 1000(8)
- 0000 0000 0001 0000(16)
- 0000 0000 0010 0000(32)
我们从中就可以发现,所有为2的整数的次方的数,二进制中都只有一个1,这个时候我们又可以拿按位与来玩了
我们可以先拿这个数减1,将最后一个1去除,例如:
可以看到,减完后,最后位为1的后面所有位数全部为1了。这个时候我们拿它跟原本拿个数想与,看是否会等于0
由于2的N次方的数二进制表示是第1位为1,其余为0,而x-1(假如x为2的N次方)得到的数的二进制表示恰恰是第1位为0,其余为1,两者相与,得到的结果就为0,否则结果肯定不为0。
(n & (n - 1))
代码如下所示:
int main()
{
int n;
scanf("%d", &n);
if ((n & (n - 1)) == 0) printf("yes");
else printf("No");
return 0;
}
教学视频如下所示: