我是小小強，這是我的第6篇原創(chuàng)文章，閱讀需要大約10分鐘。

題目

LintCode:二進制求和

描述

給定兩個二進制字符串，返回他們的和（用二進制表示）。

樣例

a = 11
b = 1
返回 100

思路

二進制相加，主要考慮進位的情況，每位在進行相加之后，要判斷之前有無進位的情況，如果有，本位要進行加1處理，同時還要考慮是否要再次向高位進位。相加結(jié)果的二進制串長度是有可能超過原數(shù)的。
最直接的方法將二進制串轉(zhuǎn)換為整數(shù)，進行相加，然后將結(jié)果再轉(zhuǎn)換為二進制串。

實現(xiàn)

非遞歸實現(xiàn)

1. java實現(xiàn)

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;
    }
}

2. 結(jié)果分析
   結(jié)果：結(jié)果通過了LintCode的要求。
   分析：這種實現(xiàn)比較好理解，但是實現(xiàn)起來卻沒什么巧妙之處。

其它優(yōu)化參考

lintcode 二進制求和 給定兩個二進制字符串，返回他們的和
LIntCode-二進制求和
Short AC solution in Java with explanation

優(yōu)秀代碼

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();
    }
}