Java实现超2^64大数是否为2的幂的判断方案问询

核心思路 #

2的幂的本质是仅包含质因数2，对应十进制的特征：

• 除了"1"（2⁰），所有2的幂的十进制数结尾只能是2、4、6、8（不会是0，因为质因数不含5）
• 反复将数除以2，最终能得到"1"的就是2的幂，中途若无法整除则不是

基于此，我们可以通过字符串模拟除法操作来实现判断，无需依赖大数类。

具体实现步骤 #

1. 预处理输入：
   • 去除字符串前导零（如"0032"转为"32"）
   • 特殊值判断：若处理后是"1"，直接返回1；若为"0"或结尾是0，直接返回0
2. 循环除以2：
   • 实现字符串除以2的逻辑，每次检查是否能整除
   • 若不能整除，返回0；若能整除，更新字符串为商
   • 直到字符串变为"1"，返回1

Java代码实现 #

public class PowerOfTwoChecker {
    public static int isPowerOfTwo(String num) {
        // 预处理：去除前导零
        num = removeLeadingZeros(num);
        
        // 特殊情况判断
        if (num.equals("1")) {
            return 1;
        }
        if (num.equals("0") || num.charAt(num.length() - 1) == '0') {
            return 0;
        }
        
        // 循环除以2，直到变为1或无法整除
        while (!num.equals("1")) {
            // 检查是否能被2整除，同时得到除以2后的结果
            String[] divideResult = divideByTwo(num);
            if (!divideResult[1].equals("0")) { // 余数不为0，无法整除
                return 0;
            }
            num = divideResult[0];
            num = removeLeadingZeros(num);
        }
        
        return 1;
    }
    
    // 去除字符串前导零
    private static String removeLeadingZeros(String num) {
        int startIndex = 0;
        while (startIndex < num.length() - 1 && num.charAt(startIndex) == '0') {
            startIndex++;
        }
        return num.substring(startIndex);
    }
    
    // 字符串除以2，返回数组：[商, 余数]
    private static String[] divideByTwo(String num) {
        StringBuilder quotient = new StringBuilder();
        int remainder = 0;
        
        for (int i = 0; i < num.length(); i++) {
            int digit = num.charAt(i) - '0';
            int current = remainder * 10 + digit;
            int q = current / 2;
            remainder = current % 2;
            
            // 避免前导零：如果商还没开始（长度为0）且q为0，跳过
            if (!(quotient.length() == 0 && q == 0)) {
                quotient.append(q);
            }
        }
        
        // 处理商为空的极端情况（如输入"0"，但前序逻辑已过滤）
        String qStr = quotient.length() == 0 ? "0" : quotient.toString();
        return new String[]{qStr, String.valueOf(remainder)};
    }
    
    // 测试示例
    public static void main(String[] args) {
        System.out.println(isPowerOfTwo("1"));      // 1
        System.out.println(isPowerOfTwo("2"));      // 1
        System.out.println(isPowerOfTwo("16"));     // 1
        System.out.println(isPowerOfTwo("1024"));   // 1
        System.out.println(isPowerOfTwo("100"));    // 0
        System.out.println(isPowerOfTwo("3"));      // 0
        System.out.println(isPowerOfTwo("000128")); // 1
        System.out.println(isPowerOfTwo("18446744073709551616")); // 2^64，返回1
    }
}

代码说明 #

• removeLeadingZeros：处理输入的前导零，避免后续判断出错
• divideByTwo：手动实现字符串除以2的逻辑，返回商和余数，完全不依赖大数类
• 主逻辑通过循环逐步缩小数值，直到得到"1"或发现无法整除，保证对超大数的兼容性

内容的提问来源于stack exchange，提问作者B DRUTHI