小于给定数字的最大2的幂：Java实现方案

1. 概述

本文探讨如何在 Java 中找出小于给定数字的最大 2 的幂。

以输入值 9 为例，我们的目标是返回 8，因为 $ 2^3 = 8 < 9 $，而下一个 $ 2^4 = 16 > 9 $，不符合条件。

⚠️ 注意：输入必须大于 1。
最小有效输入为 2（此时结果为 $ 2^0 = 1 $），因此我们只处理 input > 1 的情况。

---

2. 暴力迭代法（Naive Approach）

思路很简单：从 $ 2^0 = 1 $ 开始，不断乘以 2，直到下一个 2 的幂不小于输入为止。上一个值就是答案。

✅ 简单粗暴，适合理解逻辑。

public long findLargestPowerOf2LessThanTheGivenNumber(long input) {
    Assert.isTrue(input > 1, "Invalid input");
    long firstPowerOf2 = 1;
    long nextPowerOf2 = 2;
    while (nextPowerOf2 < input) {
        firstPowerOf2 = nextPowerOf2;
        nextPowerOf2 = nextPowerOf2 * 2;
    }
    return firstPowerOf2;
}

✅ 示例解析（input = 9）

迭代	firstPowerOf2	nextPowerOf2	条件判断
初始	1	2	2 < 9 → 继续
1	2	4	4 < 9 → 继续
2	4	8	8 < 9 → 继续
3	8	16	16 < 9 ❌ 退出

最终返回 8，正确。

✅ 测试验证

assertEquals(8, findLargestPowerOf2LessThanTheGivenNumber(9));
assertEquals(16, findLargestPowerOf2LessThanTheGivenNumber(32));

⚠️ 时间复杂度

• O(log₂N)
  每次乘 2，循环次数约为 $ \log_2(N) $，比如 9 需要 3 次。

虽然效率尚可，但乘法运算不如位运算快。下面我们看看更高效的方案。

---

3. 使用 Math.log 计算 log₂

我们知道：
$ \log_2(x) $ 表示 $ x $ 是 $ 2 $ 的多少次幂。
例如：$ \log_2(8) = 3 $，$ \log_2(16) = 4 $。

但问题是：如果输入正好是 2 的幂（如 32），我们想要的是 小于它 的最大 2 的幂，也就是 16，而不是 32。

✅ 解决方案

• 如果输入是偶数（可能是 2 的幂），先减 1，避免取到自身。
• 用换底公式计算 $ \log_2(x) = \frac{\log_{10}(x)}{\log_{10}(2)} $
• 向下取整后，再用 Math.pow(2, power) 得到结果。

public long findLargestPowerOf2LessThanTheGivenNumberUsingLogBase2(long input) {
    Assert.isTrue(input > 1, "Invalid input");
    long temp = input;
    if (input % 2 == 0) {
        temp = input - 1;
    }
    long power = (long) (Math.log(temp) / Math.log(2));
    long result = (long) Math.pow(2, power);
    return result;
}

✅ 示例（input = 9）

• temp = 9（奇数，不减）
• $ \log_{10}(9) ≈ 0.9542 $，$ \log_{10}(2) ≈ 0.3010 $
• $ \log_2(9) ≈ 3.17 $ → 取整为 3
• $ 2^3 = 8 $，返回 8 ✅

✅ 测试

assertEquals(8, findLargestPowerOf2LessThanTheGivenNumberUsingLogBase2(9));
assertEquals(16, findLargestPowerOf2LessThanTheGivenNumberUsingLogBase2(32)); // 32 是 2^5，减1后算 log 得 2^4=16

⚠️ 注意点

• Math.pow 内部其实也是循环或指数运算，**本质复杂度仍是 O(log₂N)**。
• 浮点计算存在精度风险（比如 log 结果是 2.99999 被截断成 2），但在整数范围内通常没问题。
• 不如位运算“干净”，但数学思路清晰。

---

4. 位运算左移法（Bitwise Shift）

2 的幂在二进制中很有特点：

幂次	值	4位二进制
2⁰	1	0001
2¹	2	0010
2²	4	0100
2³	8	1000

规律：只有 1 位是 1，其余为 0。

我们可以通过 1 << n 快速得到 $ 2^n $。

✅ 实现代码

public long findLargestPowerOf2LessThanTheGivenNumberUsingBitShiftApproach(long input) {
    Assert.isTrue(input > 1, "Invalid input");
    long result = 1;
    long powerOf2;
    for (long i = 0; i < Long.BYTES * 8; i++) {
        powerOf2 = 1 << i;
        if (powerOf2 >= input) {
            break;
        }
        result = powerOf2;
    }
    return result;
}

✅ 示例（input = 9）

i	1 << i	powerOf2	是否 < 9	result
0	1	1	是	1
1	2	2	是	2
2	4	4	是	4
3	8	8	是	8
4	16	16	否 ❌	返回 8

✅ 测试

assertEquals(8, findLargestPowerOf2LessThanTheGivenNumberUsingBitShiftApproach(9));
assertEquals(16, findLargestPowerOf2LessThanTheGivenNumberUsingBitShiftApproach(32));

✅ 优势

• 位移操作比乘法更快，尤其在底层优化中。
• 时间复杂度仍是 **O(log₂N)**，但常数因子更小。

✅ 推荐在性能敏感场景使用。

---

5. 利用位与特性：n & (n-1) == 0

这是一个经典技巧：
一个数 n 是 2 的幂，当且仅当 n & (n - 1) == 0

✅ 原理

• 2 的幂：二进制只有一个 1，如 1000（8）
• n-1：变成 0111（7）
• 1000 & 0111 = 0000

而其他数不具备这个性质。

✅ 实现思路

从 input - 1 开始往下遍历，找到第一个满足 i & (i-1) == 0 的数，即为小于 input 的最大 2 的幂。

public long findLargestPowerOf2LessThanTheGivenNumberUsingBitwiseAnd(long input) { 
    Assert.isTrue(input > 1, "Invalid input");
    long result = 1;
    for (long i = input - 1; i > 1; i--) {
        if ((i & (i - 1)) == 0) {
            result = i;
            break;
        }
    }
    return result;
}

✅ 示例（input = 9）

• 从 i = 8 开始
• 8 & 7 = 1000 & 0111 = 0000 → 成立，返回 8 ✅

✅ 测试

assertEquals(8, findLargestPowerOf2LessThanTheGivenNumberUsingBitwiseAnd(9));
assertEquals(16, findLargestPowerOf2LessThanTheGivenNumberUsingBitwiseAnd(32));

⚠️ 缺点

• **最坏时间复杂度 O(N/2)**，比如输入是 2 的幂时，要从 N-1 遍历到 N/2。
• 比如 input=32，要从 31 一路试到 16，效率很低。

❌ 不推荐用于大数场景，但这个技巧本身值得记住，常用于判断是否为 2 的幂。

---

6. 总结

方法	时间复杂度	优点	缺点
暴力乘法	O(log₂N)	简单易懂	乘法较慢
Math.log + 换底	O(log₂N)	数学直观	浮点精度风险，pow开销大
位左移（推荐）	O(log₂N)	位运算高效，逻辑清晰	需理解位操作
位与判断（n&(n-1)）	O(N/2) 最坏	技巧巧妙，适合小范围	大数性能差

✅ 推荐做法

• 首选位左移法：效率高，代码清晰，无精度问题。
• 如果只是判断是否为 2 的幂，用 (n & (n-1)) == 0 非常高效。
• Math.log 方法可用于数学建模，但生产环境慎用浮点运算。

所有示例代码及单元测试已上传至 GitHub：https://github.com/baomidou/tutorials/tree/master/java-math-powers