二进制数相加Java代码特定测试用例返回空字符串求助

嘿，我一眼就看出问题所在了——你的代码在处理超长二进制字符串时发生了整数溢出，这才导致返回空字符串。

为什么会返回空？ #

你用long类型来存储二进制转换后的数值，但long是64位有符号整数，最大值只有2^63 - 1（约9e18）。而你的测试用例里，A和B都是超长二进制串，它们的数值早就超过了long的范围，相加后直接溢出变成了负数。再看你的bin()方法：

public String bin(long A){
    StringBuilder sb = new StringBuilder();
    while(A>0){ // 负数的话这个循环根本不会执行！
        sb.append(A%2);
        A/=2;
    }
    String s=sb.reverse().toString();
    return s;
}

当A是负数时，while(A>0)的条件不满足，StringBuilder里啥都没有，最后返回的自然是空字符串。

另外还有个小隐患：num()方法里用Math.pow(2, ...)计算权重，Math.pow返回的是double类型，当指数较大时会有精度丢失的风险，也可能导致转换错误。

正确的解决思路：模拟手工二进制加法 #

既然超长二进制串无法用整数类型存储，那我们就模拟平时手工算二进制加法的过程：从两个字符串的末尾开始，逐位相加，记录进位，最后把结果反转过来就是正确的二进制串。

修改后的代码 #

public class Solution {
    public String addBinary(String A, String B) {
        StringBuilder sb = new StringBuilder();
        int i = A.length() - 1;
        int j = B.length() - 1;
        int carry = 0; // 记录进位

        // 从末尾开始遍历两个字符串，直到所有位都处理完，且没有进位
        while (i >= 0 || j >= 0 || carry > 0) {
            int sum = carry;
            // 取A当前位的数值（如果还有位的话）
            if (i >= 0) {
                sum += A.charAt(i--) - '0';
            }
            // 取B当前位的数值（如果还有位的话）
            if (j >= 0) {
                sum += B.charAt(j--) - '0';
            }
            // 当前位的结果是sum%2，进位是sum/2
            sb.append(sum % 2);
            carry = sum / 2;
        }

        // 因为我们是从末尾开始加的，所以要反转字符串得到正确顺序
        return sb.reverse().toString();
    }
}

代码解释 #

• 用两个指针i和j分别指向A和B的末尾，从后往前逐位处理
• carry变量记录每一步的进位，初始为0
• 每次循环计算当前位的总和（包括进位），当前位的结果是sum%2，新的进位是sum/2
• 循环继续的条件是：还有位没处理，或者还有进位没处理（比如两个最高位相加后还有进位的情况）
• 最后反转StringBuilder，得到正确的二进制顺序

这个方法不管二进制串多长都能处理，完全不会有溢出问题，而且效率也很高，时间复杂度是O(max(n,m))，n和m分别是A和B的长度。

内容的提问来源于stack exchange，提问作者Chinmay Garg