本文介绍如何在 java 中高效判断一个可能超过 long 范围的正整数（以字符串形式给出）是否为 2 的幂，避免类型溢出与高开销转换，提供两种纯字符串模拟算法及优化思路。
本文介绍如何在 java 中高效判断一个可能超过 long 范围的正整数（以字符串形式给出）是否为 2 的幂，避免类型溢出与高开销转换，提供两种纯字符串模拟算法及优化思路。
在处理大整数问题时，若输入数字长度可达 21 位（即可能远超 Long.MAX_VALUE ≈ 9.2×10¹⁸），直接使用 Long.parseLong() 或 BigInteger（题目明确禁用）将导致运行时异常或编译失败。此时必须基于字符串实现数学逻辑——而判断“是否为 2 的幂”这一问题，核心在于：所有 2 的正整数幂在十进制下均唯一对应某个特定值，且其二进制表示仅含单个 1；但本题无法转二进制（字符串太长），故需反向构造 + 字符串比较。
✅ 推荐解法：正向倍增模拟（字符串乘 2）
不尝试对输入做除法（易因多次 parseInt 溢出或抛 NumberFormatException），而是从 "1" 开始，不断将其乘以 2（字符串模拟），直到结果 ≥ 输入字符串为止。若某次结果恰好等于输入，则返回 1；否则返回 0。
该方法时间复杂度为 O(k × n)，其中 k 是目标幂次（最多约 70，因 2⁷⁰ ≈ 1.2×10²¹），n 是当前数字位数，整体高效可控。
public static int power(String s) {
// 去除前导零（如 "00128" → "128"），确保格式规范
s = s.replaceFirst("^0+", "");
if (s.isEmpty() || s.equals("0")) return 0;
if (s.equals("1")) return 1; // 2^0 = 1
String p = "1";
int pLen = 1;
int sLen = s.length();
// 循环条件：当前幂 p 的位数更少，或位数相同但字典序更小
while (pLen < sLen || (pLen == sLen && p.compareTo(s) < 0)) {
// 字符串乘2：从低位到高位模拟竖式乘法
StringBuilder doubled = new StringBuilder(pLen + 1);
doubled.setLength(pLen + 1); // 预分配空间
int carry = 0;
// 从右往左遍历每一位
for (int i = pLen - 1; i >= 0; i--) {
int digit = (p.charAt(i) - '0') * 2 + carry;
doubled.setCharAt(i + 1, (char) ('0' + digit % 10));
carry = digit / 10;
}
doubled.setCharAt(0, (char) ('0' + carry));
// 去除前导零（若最高位无进位，则截掉）
p = carry == 0 ? doubled.substring(1) : doubled.toString();
pLen = p.length();
}
return p.equals(s) ? 1 : 0;
}? 关键细节说明：
- 使用 StringBuilder 避免频繁字符串拼接；
- replaceFirst("^0+", "") 处理非法前导零输入（健壮性必备）；
- 比较采用 String.compareTo()：当两字符串等长时，字典序等价于数值大小序（因均为纯数字）；
- 进位处理保证了多位乘法的正确性（如 "49" × 2 = "98"，"50" × 2 = "100"）。
⚙️ 进阶优化：原地缓冲区（节省内存）
若对空间敏感（如嵌入式或高频调用场景），可复用单个 StringBuffer，将当前幂值右对齐存储，动态维护有效起始索引：
public static int power(String s) {
s = s.replaceFirst("^0+", "");
if (s.isEmpty() || s.equals("0")) return 0;
if (s.equals("1")) return 1;
int len = s.length();
StringBuffer buf = new StringBuffer(len);
buf.setLength(len);
int start = len - 1; // 当前数字在buf中最右一位的位置
buf.setCharAt(start, '1');
while (start > 0 || buf.charAt(0) < s.charAt(0)) {
int carry = 0;
// 从有效最低位开始乘2
for (int i = len - 1; i >= start; i--) {
int digit = (buf.charAt(i) - '0') * 2 + carry;
buf.setCharAt(i, (char) ('0' + digit % 10));
carry = digit / 10;
}
if (carry > 0) {
start--;
if (start < 0) return 0; // 溢出至更高位，但已超输入长度
buf.setCharAt(start, '1');
}
}
return buf.substring(start).equals(s) ? 1 : 0;
}此版本避免创建中间字符串，显著降低 GC 压力，适合大规模批量校验。
? 注意事项与边界处理
- ✅ 必须处理前导零："0001"、"0" 等非法/边缘输入；
- ✅ 显式排除 "0"：0 不是任何正整数幂（2ⁿ > 0, ∀n∈ℕ）；
- ✅ 快速特判 "1"：对应 2⁰，避免空循环；
- ⚠️ 不可依赖 Integer.parseInt() 或 Long.parseLong()：题目明确输入可超 64 位，强制字符串处理；
- ? 备选方案（预计算查表）：若输入长度 ≤ 21，共仅 67 个合法 2 的幂（2⁰ 到 2⁶⁶），可静态初始化 Set<String> 存储全部，实现 O(1) 查询：
private static final Set<String> POWERS_OF_TWO = Set.of(
"1", "2", "4", "8", "16", "32", "64", "128", /* ... up to "73786976294838206464" */
);
// then: return POWERS_OF_TWO.contains(s.replaceAll("^0+", ""));该方案极致简洁，适用于测试数据固定、内存充裕的场景。
综上，字符串倍增法兼具正确性、可读性与工程实用性，是解决超大数 2 的幂判定问题的标准范式。
