[算法很美](位运算_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去除,例如:

img

可以看到,减完后,最后位为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;
}

教学视频如下所示:

本文链接:

https://nullcode.fun/102.html
1 + 9 =
快来做第一个评论的人吧~