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

题目

读入 n，判断是否为 2 的幂

思路

本题判断 n 是否为 2 的幂（如 1, 2, 4, 8…）。

常用写法：n>0 && (n & (n-1)) == 0；或不断 n/=2 直到剩 1 或出现奇数因子。

解题分析

2 的幂在二进制里只有一位是 1。n>0 且 n-1 会把最低那位置 0 并产生借位，于是 n 与 n-1 按位与为 0。n=0 不是 2 的幂，别漏判。

完整程序

#include <stdio.h>

int main(void)
{
    unsigned n;
    if (scanf("%u", &n) != 1) {
        return 1;
    }
    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