[算法很美](位运算_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;
}

教学视频如下所示：

本文链接：