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

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

本文详解如何在 Java 中高效判断任意长度的正整数字符串（可能远超 long 范围，如 21 位以上）是否为 2 的幂，避免数值溢出，不依赖 BigInteger 或外部库，通过字符串模拟乘法或位运算思想实现。

本文详解如何在 java 中高效判断任意长度的正整数字符串（可能远超 `long` 范围，如 21 位以上）是否为 2 的幂，避免数值溢出，不依赖 `biginteger` 或外部库，通过字符串模拟乘法或位运算思想实现。

在算法题与系统编程中，常需判断一个极大整数是否为 2 的幂（即形如 $2^n, n \geq 0$ 的数）。当输入以字符串形式给出（如 "123456789012345678901"），且长度可达 21 位甚至更长时，传统 Long.parseLong() 或 BigInteger（题目禁用）均不可行。此时必须基于字符串操作设计无溢出解法。

核心思路有二：正向生成法（推荐）与反向除法模拟（易错、低效）。由于字符串无法直接取模或整除，反向不断除以 2 并校验余数的方式需频繁解析子串、易触发 NumberFormatException 且逻辑复杂；而正向生成法——从 "1" 开始，反复乘以 2 得到 "2", "4", "8", ...，直至结果 ≥ 目标字符串——天然规避溢出，逻辑清晰、可验证性强，是本题最优实践。

✅ 正向生成法（双指针 + 字符串乘法模拟）

我们维护一个 StringBuffer 表示当前幂次值（初始为 "1"），并始终右对齐存储于缓冲区中（高位补空格或通过 start 索引定位有效数字起始位置）。每次执行「×2」操作：从最低位开始逐位计算 digit × 2 + carry，更新当前位与进位。若最高位产生进位，则 start 左移一位并置 '1'。

以下是精简、健壮的 Java 实现：

public static int power(String s) {
    // 预处理：去除前导零（如 "000128" → "128"）
    s = s.replaceFirst("^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;
        }
        // 处理最高位进位
        if (carry > 0) {
            start--;
            if (start <h3>? 关键细节说明</h3>

时间复杂度：最多生成约 $\log_2(10^{\text{size}}) \approx \text{size} \times \log_2{10} \approx 3.3 \times \text{size}$ 个幂次，每次乘法耗时 $O(\text{size})$，总体 $O(\text{size}^2)$，对 21 位输入完全可行（
空间优化：仅用单个 StringBuffer 和两个整型变量（start, carry），内存占用恒定 $O(\text{size})$。
边界安全：
- replaceFirst("^0+", "") 处理非法前导零；
- 显式检查 "" 和 "0"；
- start
比较逻辑：利用字符串字典序（charAt(0) 对比）快速剪枝，仅当位数相同且首字符相等时才进入完整匹配。

⚠️ 注意事项与常见误区

❌ 不要尝试 Integer.parseInt(A) 或 Long.parseLong(A)：题目明确指出输入可能超 long 范围（如 "18446744073709551616" 即 $2^{64}$），强制解析必抛 NumberFormatException。
❌ 避免递归或深度嵌套字符串拼接：A = Integer.toString(...) 在循环中会引发大量临时对象，导致 TLE 或 OOM。
✅ 可选优化：若已知输入长度上限（如 ≤21），可预存全部 67 个 ≤ $10^{21}$ 的 2 的幂（从 "1" 到 "2097152..."）至 HashSet，实现 $O(1)$ 查询。但本解法通用性更强，无需硬编码。