判断一个数是否为 2 的幂

1. 概述

在本篇文章中，我们将讨论如何判断一个正整数是否是 2 的幂。

首先，我们会明确问题定义并举例说明。然后，我们将介绍三种不同的解法：

循环除以 2
二分查找
位运算（推荐）

每种方法都会分析其实现原理和时间复杂度，帮助你根据实际场景选择最合适的方式。

2. 问题定义

给定一个正整数 N，我们需要判断它是否是 2 的幂。即是否存在一个整数 x，使得 N = 2^x。

示例

N = 1 → 是 2 的幂（2⁰）
N = 8 → 是 2 的幂（2³）
N = 15 → 不是 2 的幂
N = 0 → 不是 2 的幂（不符合正整数条件）

3. 循环除以 2 法

3.1 思路解析

2 的幂在二进制中表现为一个 1 后面跟着若干个 0（如 1000...000）。因此，只要不断除以 2，最终结果应为 1。

3.2 实现代码

public boolean isPowerOfTwoUsingLoop(int N) {
    if (N <= 0) return false;
    while (N % 2 == 0) {
        N /= 2;
    }
    return N == 1;
}

3.3 时间复杂度

✅ 时间复杂度：O(log N)
⚠️ 每次除以 2，最多循环 log₂N 次

4. 二分查找法

4.1 思路解析

我们可以用二分法查找是否存在一个整数 x，使得 2^x == N。查找范围为 0 ~ log₂N。

4.2 实现代码

public boolean isPowerOfTwoUsingBinarySearch(int N) {
    if (N <= 0) return false;

    int low = 0, high = (int)(Math.log(N) / Math.log(2));
    while (low <= high) {
        int mid = (low + high) / 2;
        int power = (int) Math.pow(2, mid);
        if (power == N) return true;
        else if (power < N) low = mid + 1;
        else high = mid - 1;
    }
    return false;
}

4.3 时间复杂度

✅ 时间复杂度：O(log log N)
⚠️ 比循环法更快，但需要调用 Math.pow() 和 Math.log()，在某些场景下可能不如位运算高效

5. 位运算法（推荐）

5.1 思路解析

2 的幂在二进制中是 1000...000，减 1 后变成 0111...111。两者进行按位与（&）结果应为 0。

✅ 核心公式：(N & (N - 1)) == 0

⚠️ 注意：必须确保 N > 0，因为 0 也会满足 (N & (N - 1)) == 0，但它不是 2 的幂

5.2 实现代码

public boolean isPowerOfTwoUsingBitmask(int N) {
    return N > 0 && (N & (N - 1)) == 0;
}

5.3 时间复杂度

✅ 时间复杂度：O(1)
⚠️ 仅需一次位运算，性能最优，推荐使用

6. 总结

我们介绍了三种判断一个数是否为 2 的幂的方法：

方法	时间复杂度	是否推荐	说明
✅ 循环除以2	O(log N)	否	简单直观，但效率一般
🔍 二分查找	O(log log N)	否	比循环快，但依赖浮点运算
💡 位运算	O(1)	✅ 推荐	高效简洁，推荐在实际开发中使用

✅ 推荐使用位运算：

return N > 0 && (N & (N - 1)) == 0;

这是一行代码解决该问题的最佳实践，广泛应用于 Java、C++、Python 等语言中。

Persistence

REST

Security