LeetCode 每日一题 [28] 二进制求和

LeetCode 二进制求和 [简单]

给你两个二进制字符串，返回它们的和（用二进制表示）。

输入为 非空 字符串且只包含数字 1 和 0。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-binary

示例 1:

输入: a = "11", b = "1"
输出: "100"

示例 2:

输入: a = "1010", b = "1011"
输出: "10101"

提示：

每个字符串仅由字符 '0' 或 '1' 组成。
1 <= a.length, b.length <= 10^4
字符串如果不是 "0" ，就都不含前导零。

题目分析

解法1

使用Java 提供的API

解法2

逐位计算
初始进位 carry = 0 ；如果数字 aa 的最低位是 1，则将 1 加到进位 carrycarry；同理如果数字 bb 的最低位是 1，则也将 1 加到进位。此时最低位有三种情况：(00)2,(01)2,(10)2
然后将 carrycarry 的最低位作为最低位的值，将 carrycarry 的最高位移至下一位继续计算。
重复上述步骤，直到数字 aa 和 bb 的每一位计算完毕。最后如果 carrycarry 的最高位不为 0，则将最高位添加到计算结果的末尾。最后翻转结果得到求和结果

解法3

XOR 操作得到两个数字无进位相加的结果。

1

进位和两个数字与操作结果左移一位对应。

2
现在问题被简化为：首先计算两个数字的无进位相加结果和进位，然后计算无进位相加结果与进位之和。同理求和问题又可以转换成上一步，直到进位为 0 结束。

算法

把 a 和 b 转换成整型数字 x 和 y，x 保存结果，y 保存进位。
当进位不为 0：y != 0：
计算当前 x 和 y 的无进位相加结果：answer = x^y。
计算当前 x 和 y 的进位：carry = (x & y) << 1。
完成本次循环，更新 x = answer，y = carry。
返回 x 的二进制形式。

代码实现

public class LeetCode_28_AddBinary {

    public static void main(String[] args) {
        String a = "11", b = "1";
        String s1 = addBinary(a, b);
        String s2 = addBinary2(a, b);
        String s3 = addBinary2(a, b);
        System.out.println(s1);
        System.out.println(s2);
        System.out.println(s3);
    }

    public static String addBinary3(String a, String b) {
        BigInteger x = new BigInteger(a, 2);
        BigInteger y = new BigInteger(b, 2);
        BigInteger zero = new BigInteger("0", 2);
        BigInteger carry, answer;
        while (y.compareTo(zero) != 0) {
            answer = x.xor(y);
            carry = x.add(y).shiftLeft(1);
            x = answer;
            y = carry;
        }
        return x.toString(2);
    }

    public static String addBinary2(String a, String b) {
        int n = a.length(), m = b.length();
        if (n < m) {
            return addBinary2(b, a);
        }
        int L = Math.max(n, m);
        StringBuilder sb = new StringBuilder();
        int carry = 0, j = m - 1;
        for (int i = L - 1; i > -1; i--) {
            if (a.charAt(i) == '1') {
                ++carry;
            }
            if (j > -1 && b.charAt(j--) == '1') {
                ++carry;
            }
            if (carry % 2 == 1) {
                sb.append('1');
            } else {
                sb.append('0');
            }
            carry /= 2;
        }
        if (carry == 1) {
            sb.append('1');
        }
        return sb.reverse().toString();
    }

    public static String addBinary(String a, String b) {
        return Integer.toBinaryString(Integer.parseInt(a, 2) + Integer.parseInt(b, 2));
    }
}