判断一个大整数字符串是否为 2 的幂-java教程-PHP中文网

判断一个大整数字符串是否为 2 的幂

本文详解如何在 Java 中高效判断一个可能超长（长度达 21 位以上，远超 long 范围）的数字字符串是否为 2 的幂，避开大数库依赖，通过字符串模拟倍增或位运算思想实现无溢出、低开销判定。

本文详解如何在 java 中高效判断一个可能超长（长度达 21 位以上，远超 `long` 范围）的数字字符串是否为 2 的幂，避开大数库依赖，通过字符串模拟倍增或位运算思想实现无溢出、低开销判定。

在算法面试与高频编程题中，“判断某数是否为 2 的幂”是一个经典问题。对普通整型（如 int/long），我们可直接用位运算技巧：n > 0 && (n & (n - 1)) == 0。但本题关键约束在于——输入以字符串形式给出，且长度可达 21 位以上（例如 "18446744073709551616"，即 2⁶⁴），已超出 long（最大约 2⁶³−1）甚至 unsigned long 表达范围，更不允许使用 BigInteger 或任何外部数学库。

此时，核心思路必须转向 字符串级别的数值操作。常见错误解法（如反复 Integer.parseInt(A)/2）会因溢出直接抛异常；而暴力除以 2 直到为 1 的策略，若用字符串模拟除法虽可行，但时间复杂度高（每次除法 O(n)，最多 log₂(N) 次 → 总体 O(n log N)），且代码冗长易错。

更优策略是 反向构造 + 字符串比较：从 "1" 开始，不断“乘以 2”（字符串模拟），生成所有不超过目标长度的 2 的幂，一旦相等即返回 1；若超过目标值仍未匹配，则返回 0。该方法逻辑清晰、边界可控，且实际运行中最多迭代约 70 次（因为 2⁷⁰ ≈ 1e21），效率极高。

以下是推荐的高性能实现（单 StringBuffer 复用，空间最优）：

public static int power(String s) {
    // 去除前导零（如 "00128" → "128"），确保格式标准化
    s = s.replaceAll("^0+", "");
    if (s.isEmpty() || s.equals("0")) return 0; // 边界：空串或零非2的幂

    int size = s.length();
    StringBuffer buf = new StringBuffer(size);
    buf.setLength(size); // 预分配容量，避免动态扩容

    // 初始值：2^0 = "1"，右对齐存储（末位为个位）
    int start = size - 1;
    buf.setCharAt(start, '1');

    // 循环倍增：生成 2^1, 2^2, ..., 直到 >= s
    while (start > 0 || buf.charAt(0) = start; i--) {
            int digit = (buf.charAt(i) - '0') * 2 + carry;
            buf.setCharAt(i, (char) ('0' + (digit % 10)));
            carry = digit / 10;
        }
        // 若最高位产生进位，需左移一位并置 '1'
        if (carry > 0) {
            start--;
            if (start <p>✅ <strong>关键设计说明</strong>：  </p>

右对齐存储：buf 固定长度 size，数字低位存于右侧索引大的位置（如 "128" 存为 ['?','1','2','8']，start=1），便于原地倍增和进位处理；
无额外字符串创建：全程复用 StringBuffer，仅在最后 substring 一次提取结果，内存友好；
提前终止：循环条件 start > 0 || buf.charAt(0)
鲁棒性处理：严格过滤前导零、空串、零值，符合数学定义（2 的幂恒为正整数）。

⚠️ 注意事项：