C 语言第28题：读入 n，判断是否为 2 的幂

题目

从标准输入读入一个正整数 n，判断它是否为 2 的整数次幂（如 1, 2, 4, 8, 16...）。

输入格式：一行输入一个正整数 n。

输出格式：若是 2 的幂输出 yes，否则输出 no，末尾换行。

数据范围与约定：1 ≤ n ≤ 2×10⁹。

思路与算法

1. 位运算性质 n & (n - 1)
2 的幂在二进制表示下有且仅有最高位一个 1（如 8 = 1000₂）。当对其减 1 时，该二进制位变为 0，所有低位变为 1（7 = 0111₂）。两数按位与必为 0：n & (n - 1) == 0。

2. 正数边界
0 不是 2 的幂，因此完整判断为：n > 0 && (n & (n - 1)) == 0。运算速度达到 O(1)。

完整程序

#include <stdio.h>

int main(void)
{
    unsigned n;
    if (scanf("%u", &n) != 1) {
        return 1;
    }

    // 核心位运算技巧：2 的幂在二进制中有且仅有 1 个 1
    // n - 1 会将该 1 变为 0，且更低位全部变成 1
    // 因此 n & (n - 1) 为 0 且 n > 0 是判定 2 的幂的充要条件
    if (n > 0 && (n & (n - 1)) == 0) {
        printf("yes\n");
    } else {
        printf("no\n");
    }
    return 0;
}

运行示例

输入：

16

输出：

yes

其它写法

下面每种写法都是完整程序，输入输出格式与正文一致，便于对照。

循环除以 2

程序：

#include <stdio.h>

int main(void)
{
    unsigned n;
    if (scanf("%u", &n) != 1) {
        return 1;
    }
    if (n == 0) {
        printf("no\n");
        return 0;
    }
    while (n % 2 == 0) {
        n /= 2;
    }
    printf("%s\n", n == 1 ? "yes" : "no");
    return 0;
}

输入：

16

输出：

yes