题目

LintCode:二进制求和

描述

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

样例

a = 11
b = 1
返回 100

思路

二进制相加，主要考虑进位的情况，每位在进行相加之后，要判断之前有无进位的情况，如果有，本位要进行加1处理，同时还要考虑是否要再次向高位进位。相加结果的二进制串长度是有可能超过原数的。
最直接的方法将二进制串转换为整数，进行相加，然后将结果再转换为二进制串。

实现

非递归实现

java实现

public class Solution {
    /**
     * @param a a number
     * @param b a number
     * @return the result
     */
    public String addBinary(String a, String b) {
        // Write your code here
        if (a == null || b == null) {
            return null;
        }
        return parseInt2String(parseString2(a) + parseString2(b));
    }
    
     public static int parseString2(String str1){
        char c = 0;
        int sum = 0;
        for (int i = 0; i < str1.length(); i++) {
            if (str1.charAt(i) == '1'){
                sum += 1<<(str1.length()-1-i);
            }
        }
        return sum;
    }

    public static String parseInt2String(int a){
        String str = "";
        if (a == 0)
            return "0";
        while (a != 0){
            str += a % 2;
            a = a/2;
        }
        String str2 = "";
        int i = str.length();
        while (i > 0 ){
            str2+=str.charAt(i-1);
            i--;
        }
        return str2;
    }
}

结果分析
结果：结果通过了LintCode的要求。
分析：这种实现比较好理解，但是实现起来却没什么巧妙之处。

其它优化参考

lintcode 二进制求和给定两个二进制字符串，返回他们的和
 LIntCode-二进制求和
 Short AC solution in Java with explanation

优秀代码

public class Solution {
    public String addBinary(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int i = a.length() - 1, j = b.length() -1, carry = 0;
        while (i >= 0 || j >= 0) {
            int sum = carry;
            if (j >= 0) sum += b.charAt(j--) - '0';
            if (i >= 0) sum += a.charAt(i--) - '0';
            sb.append(sum % 2);
            carry = sum / 2;
        }
        if (carry != 0) sb.append(carry);
        return sb.reverse().toString();
    }
}