17370845950

n & (n - 1) == 0 且 n > 0 时，n 是 2 的幂；因其二进制仅含一个 1，该运算清除最低位 1 后得 0，但需排除 n == 0 的误判。

为什么 n & (n - 1) 能判断 2 的幂

一个正整数是 2 的幂，当且仅当它的二进制表示中**有且仅有一个 1**。例如：8 是 1000，16 是 10000。n & (n - 1) 的作用是**清除最低位的 1**。对 2 的幂来说，这个操作会把唯一的 1 也清掉，结果为 0。

但要注意前提：必须确保 n > 0。因为 0 和负数不满足 2 的幂定义，且 0 & (0 - 1) 在补码下是 0 & 0xFFFFFFFF（32 位），结果非 0，会误判。

• n == 0 必须单独排除
• n 直接返回 false（C++ 中负数不可能是 2 的幂）
• 该方法只适用于整数类型，如 int、unsigned int、long long

完整可移植的判断函数写法

标准写法需兼顾边界和类型安全。推荐使用无符号类型避免符号扩展问题，同时显式处理零值：

bool isPowerOfTwo(unsigned int n) {
    return n != 0 && (n & (n - 1)) == 0;
}

若输入可能是有符号类型（如 int），先转为无符号再判断更稳妥：

立即学习“C++免费学习笔记（深入）”；

bool isPowerOfTwo(int n) {
    if (n <= 0) return false;
    unsigned int u = static_cast(n);
    return (u & (u - 1)) == 0;
}

• 不要用 int 直接参与位运算判断，-1 或溢出行为依赖实现
• (n & (n - 1)) == 0 比 ! (n & (n - 1)) 更清晰，避免与逻辑非混淆
• 编译器通常能将该表达式优化为单条指令（如 x86 的 test + je）

常见误判场景和调试提示

实际编码中容易忽略这些细节：

• 传入 0：返回 true（如果没加 n != 0 判断）——这是最常见错误
• 传入 1：正确返回 true（1 是 2^0，1 & 0 == 0）
• 传入 INT_MIN（如 -2147483648）：有符号减法溢出，未定义行为；必须提前拦截
• 用在模板函数中时，若类型是 size_t，要确认平台位宽（如 Windows LLP64 下 size_t 是 32 位）

调试时可加断言验证关键点：

assert((n & (n - 1)) == 0 || n == 0 || (n & (n - 1)) != 0); // 至少保证不崩

其他方法对比：为什么不用 log2 或循环除法

用浮点函数或循环虽然语义直观，但有明显缺陷：

• std::log2(n) 返回浮点数，存在精度误差（如 log2(2^24) 可能略小于 24.0）
• 需要 std::floor 和 std::ceil 配合判断，开销大且不可靠
• 循环除 2（while (n % 2 == 0) n /= 2;）时间复杂度 O(log n)，而位运算是 O(1)
• 编译器很难把循环优化成位运算，尤其当 n 是运行时变量时

除非明确要求支持大整数（如 __int128 或 boost::multiprecision），否则位运算仍是首选。

真正麻烦的是跨平台大整数或需要支持任意底数幂的场景——那已经不是“2 的幂”这个简单问题了。