二进制求和【LeetCode:67】

题目：

给定两个二进制字符串，返回他们的和（用二进制表示）。
输入为非空字符串且只包含数字 1 和 0。

• 示例 1:

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

• 示例 2:

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

解析

• 补齐字符串长度，使得两个字符串等长，这样可直接遍历避免使用if一直做判断
• 其中一个字符串转char数组，把另一个字符串中的数据加上去，这样可以少复制一份数据
• 按位求和（第一版中使用if分别处理三种情况），可使用位运算得到求和结果和进位（第二版实现)

实现

• Java第一版：

执行用时2ms，超越98%

class Solution {
    public static String addBinary(String a, String b) {
        int len1 = a.length(), len2 = b.length();
        if (len1 > len2) {
            b = repeat('0', len1 - len2) + b;
        } else if (len2 > len1) {
            a = repeat('0', len2 - len1) + a;
        } 
        char[] result = a.toCharArray();
        boolean adder = false;
        for (int i = result.length - 1; i >= 0; i--) {
            char a1 = result[i];
            char b1 = b.charAt(i);
            if (a1 == '1' && b1 == '1') {
                result[i] = adder ? '1' : '0';
                adder = true;
            } else if (a1 == '0' && b1 == '0') {
                result[i] = adder ? '1' : '0';
                adder = false;
            } else {
                result[i] = adder ? '0' : '1';
                adder = adder && result[i] == '0';
            }
        }
        String s = new String(result);
        return adder ? "1" + s : s;
    }

    static String repeat(char c, int length) {
        char[] chars = new char[length];
        for (int i = 0; i < length; i++) {
            chars[i] = '0';
        }
        return new String(chars);
    }
}

• Java第二版

执行运行1ms，超越100%

针对第一版本优化：通过直接对char类型的数据求和，并使用位运算取出结果和进位

class Solution {
    public static String addBinary(String a, String b) {
        int len1 = a.length(), len2 = b.length();
        if (len1 > len2) {
            b = repeat('0', len1 - len2) + b;
        } else if (len2 > len1) {
            a = repeat('0', len2 - len1) + a;
        }
        char[] result = a.toCharArray();
        int adder = 0;
        for (int i = result.length - 1; i >= 0; i--) {
            int sumResult = result[i] + b.charAt(i) + adder - 96;
            result[i] = (char)((sumResult & 1) + 48);
            adder = sumResult >>> 1;
        }
        String s = new String(result);
        return adder == 1 ? "1" + s : s;
    }

    static String repeat(char c, int length) {
        char[] chars = new char[length];
        for (int i = 0; i < length; i++) {
            chars[i] = '0';
        }
        return new String(chars);

    }
}

题目来源：力扣（LeetCode）