判断大数是否为2的幂，只需看二进制是否只有一个1

本文深入探讨了如何在Java中高效判断超大正整数（以字符串形式给出、位数可达21位以上，远超long范围）是否为2的幂，直击类型溢出与高开销转换痛点，摒弃BigInteger和数值解析等危险或禁用手段，原创性地提出基于字符串模拟的“正向倍增法”——从"1"出发反复乘2并字符串比较，辅以进位处理、前导零清洗、字典序数值比较等精巧设计，兼顾正确性、性能与健壮性；同时提供原地缓冲区优化版降低GC压力，以及预计算查表等实用备选方案，为大数幂判定这一经典工程难题提供了清晰、可靠、可落地的标准解法。

本文介绍如何在 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 存储全部，实现 O(1) 查询：

private static final Set 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 的幂判定问题的标准范式。

理论要掌握，实操不能落！以上关于《判断大数是否为2的幂，只需看二进制是否只有一个1》的详细介绍，大家都掌握了吧！如果想要继续提升自己的能力，那么就来关注golang学习网公众号吧！