67. Add Binary

Given two binary strings, return their sum (also a binary string).
The input strings are both non-empty and contains only characters 1 or 0.
Example 1:
Input: a = "11", b = "1"
Output: "100"
Example 2:
Input: a = "1010", b = "1011"
Output: "10101"
Constraints:
Each string consists only of '0' or '1' characters.
1 <= a.length, b.length <= 10^4
Each string is either "0" or doesn't contain any leading zero.

分析

二进制数相加，主要需要考虑进位的问题。

1. 建立两个游标，分别从两个字符串从后向前遍历，对同样位置的digit相加并加上前一位的进位（carry）。
2. 其中一个字符串遍历完以后，需要对另一个继续遍历，因为可能还有进位需要处理
3. 两个字符串都遍历完以后，再看是否有进位，有的话，结果补充上进位。
   具体实现上，可以用StringBuilder/StringBuffer维护每一位相加后的结果，最后再进行reverse。

code

class Solution {
    public String addBinary(String a, String b) {
        if (a==null) return b;
        if (b==null) return a;
        StringBuilder res = new StringBuilder();
        int carry = 0;
        int p = a.length()-1, q = b.length()-1;
        while (p>=0 && q>=0) {
            int sum = carry + a.charAt(p--) - '0' + b.charAt(q--) - '0';
            carry = sum / 2;
            sum %= 2;
            res.append(sum);
        }
        String t = a;
        if (q >= 0) {
            p = q;
            t = b;
        }
        while (p>=0) {
            int sum = carry + t.charAt(p--) - '0';
            carry = sum / 2;
            sum %= 2;
            res.append(sum);
        }
        if (carry > 0) {
            res.append(carry);
        }
        res.reverse();
        return res.toString();
    }
}

延伸

如果是8进制，16进制数相加呢？
处理方法是一样的，区别是计算每一位的加和时，求模的分母不一样，对于16进制数，10-15需要转化为A-F。

code： 16进制数相加

    private static char toChar(int n) {
        if (n>=16) {
            throw new RuntimeException("illegal number: " + n);
        }
        if (n < 10) {
            return (char)(n + '0');
        }
        return (char)((n - 10) + (int)'a');
    }

    private static int toNum(char c) {
        if (c >= 'a') {
            return 10 + c -'a';
        }
        return c - '0';
    }

    public static String addTwoHexadecimal(String a, String b) {
        if (a==null) {
            return b;
        }
        if (b==null) {
            return a;
        }
        StringBuilder res = new StringBuilder();
        int p = a.length()-1, q = b.length()-1;
        int carry = 0;
        while (p>=0 && q>=0) {
            int sum = carry + toNum(a.charAt(p--)) + toNum(b.charAt(q--));
            carry = sum / 16;
            res.append(toChar(sum % 16));
        }

        String t = a;
        if (q >= 0) {
            t = b;
            p = q;
        }

        while (p >= 0) {
            int sum = carry + toNum(t.charAt(p--));
            carry = sum / 16;
            res.append(toChar(sum % 16));
        }

        if (carry > 0) {
            res.append(carry);
        }

        res.reverse();
        return res.toString();
    }