判断一个数是否是 3 的幂次方：Java 实现与算法分析
一、问题描述
给定一个整数 n，编写一个函数判断它是否是 3 的幂次方。
满足条件：存在整数 x 使得 n == 3^x。
示例：
- 输入：27 → 输出：true（3³=27）
- 输入：0 → 输出：false（3 的任何次幂都不为 0）
- 输入：-3 → 输出：false（幂次方结果为正整数）
二、解决方案
方法一：循环迭代法（通用思路）
核心思想
不断将数字除以 3，直到无法整除为止。若最终结果为 1，则是 3 的幂；否则不是。
步骤：
- 处理边界条件：
n ≤ 0直接返回 false（3 的幂必为正整数）。 - 循环除以 3，直到余数不为 0。
- 检查最终结果是否为 1。
代码实现
java">class Solution {public boolean isPowerOfThree(int n) {if (n < 1) { // 处理负数和0return false;}while (n % 3 == 0) { // 能被3整除时继续除n /= 3;}return n == 1; // 最终结果是否为1}
}
复杂度分析
- 时间复杂度：O (log₃n)，循环次数等于 3 的幂次（如 3¹⁹需要循环 19 次）。
- 空间复杂度：O (1)，仅使用常数额外空间。
优缺点
- 优点：通用，适用于判断任意数的幂（如 2 的幂、5 的幂）。
- 缺点：大数时循环次数较多（如 3¹⁹需要 19 次循环）。
方法二：数学性质法（Java 特化优化）
核心思想
利用 Java 中int类型的范围限制：
int最大值为2¹⁴⁷⁴⁸³⁶⁴⁷，3 的最大幂次方为 3¹⁹ = 1,162,261,467（3²⁰超过 int 范围）。- 若
n是 3 的幂，则1,162,261,467必能被n整除（因为 3¹⁹是 3 的所有幂的倍数）。
代码实现
java">class Solution {public static final int MAX_POWER_OF_3 = 1162261467; // 3¹⁹public boolean isPowerOfThree(int n) {return n > 0 && MAX_POWER_OF_3 % n == 0;}
}
关键细节
- 边界条件：
n > 0排除负数和 0。 - 数学原理：3¹⁹是 3 的所有幂的倍数（如 3⁰=1，3¹=3，…，3¹⁹）。若
n是 3 的幂，则必为 3¹⁹的因数。
复杂度分析
- 时间复杂度：O (1)，仅一次取模运算。
- 空间复杂度：O (1)，常数空间。
优缺点
- 优点：极致优化，常数时间复杂度。
- 缺点：依赖编程语言的整数范围（如 Java 的
int），移植性较差。
三、两种方法对比
| 维度 | 循环迭代法 | 数学性质法 |
|---|---|---|
| 通用性 | 高（任意基数的幂） | 低（仅适用于 3 的幂 + Java） |
| 时间复杂度 | O(log₃n) | O(1) |
| 空间复杂度 | O(1) | O(1) |
| 边界处理 | 显式判断（n < 1） | 隐式包含（n > 0） |
| 适用场景 | 通用场景、其他语言（如 C++） | Java 场景、追求极致性能 |
四、测试用例
| 输入（n） | 预期输出 | 解释 |
|---|---|---|
| 0 | false | 3 的幂不能为 0 |
| 1 | true | 3⁰=1 |
| 3 | true | 3¹=3 |
| 9 | true | 3²=9 |
| 27 | true | 3³=27 |
| 45 | false | 45=3²×5，含其他质因数 |
| -3 | false | 负数不可能是 3 的幂 |
| 1162261467 | true | 3¹⁹（最大 3 的幂） |
五、扩展思考
- 如何判断 2 的幂？
- 循环法：同上。
- 数学法：利用位运算（n & (n-1) == 0），更高效。
- 大数处理：若
n超过int范围（如long），数学法需调整最大幂值。 - 质因数分解：3 的幂的质因数只能是 3。若
n的质因数包含其他数（如 5），则不是 3 的幂。
六、总结
- 循环迭代法：通用、易理解，适合教学和通用场景。
- 数学性质法：Java 特化优化，极致性能，适合已知整数范围的场景。
- 选择建议：根据语言特性和场景选择。若需跨语言或通用逻辑，选循环法；若追求极致性能（Java），选数学法。
七、完整代码（含测试）
java">class Solution {// 方法一：循环迭代法public boolean isPowerOfThreeLoop(int n) {if (n < 1) return false;while (n % 3 == 0) n /= 3;return n == 1;}// 方法二：数学性质法private static final int MAX_POWER = 1162261467;public boolean isPowerOfThreeMath(int n) {return n > 0 && MAX_POWER % n == 0;}// 测试示例public static void main(String[] args) {Solution solution = new Solution();int[] testCases = {0, 1, 3, 9, 27, 45, -3, 1162261467};for (int n : testCases) {boolean loopResult = solution.isPowerOfThreeLoop(n);boolean mathResult = solution.isPowerOfThreeMath(n);System.out.printf("n=%-10d 循环法：%-5b 数学法：%-5b%n", n, loopResult, mathResult);}}
}
输出结果：
java">n=0 循环法：false 数学法：false
n=1 循环法：true 数学法：true
n=3 循环法：true 数学法：true
n=9 循环法：true 数学法：true
n=27 循环法：true 数学法：true
n=45 循环法：false 数学法：false
n=-3 循环法：false 数学法：false
n=1162261467 循环法：true 数学法：true 
