面试题2：二进制加法（Java版）

题目：输入两个表示二进制的字符串，请计算它们的和，并以二进制字符串的形式输出。例如，输入的二进制字符串分别是"11"和"10"，则输出"101"。

public static String addBinary(String a, String b) {
    // 创建一个StringBuilder对象来对二进制字符串进行 *** 作
    StringBuilder result = new StringBuilder();
    // i j 为字符串中字符的索引，因为二进制加法是按从右到左相加进位
    // 所以i j都从字符串最后一个字符起步往左边走。
    int i = a.length() - 1;
    int j = b.length() - 1;
    // carry是加法过程中的进位数
    int carry = 0;
    // 因为两个二进制数长度可能会不一样
    // 所以只要i >= 0 或者 j >= 0时就进入循环
    while (i >= 0 || j >= 0) {
        // 因为如果两个二进制的长度不一样会导致
        // i或j中一个数小于0所以当小于0时默认为0
        int digitA = i >= 0 ? a.charAt(i--) - '0' : 0;
        int digitB = j >= 0 ? b.charAt(j--) - '0' : 0;
        int sum = digitA + digitB + carry;
        // 当sum >= 2时在二进制中讲进位
        // 所以当sum >= 2时进位数为1反之则为0
        carry = sum >= 2 ? 1 : 0;
        // 当sum >= 2时将进位，所以sum = sum - 2
        // 否则sum不变
        sum = sum >= 2 ? sum - 2 : sum;
        // 将sum追加到二进制字符串中
        result.append(sum);
    }
    // 如果两个数到最左端的数都加完了后
    // 进位数为1则将进位数追加到二进制字符串中
    if (carry == 1) {
        result.append(1);
    }

    // 因为最先加入的数最后在最左边，但是我们加法是从
    // 最右边开始算的所以结果的顺序需要颠倒一下
    return result.reverse().toString();
}