Given two binary strings, return their sum (also a binary string).
For example,
a = "11"
b = "1"
Return "100".
解题思路：
这题比较基础，但想写对也不太容易。
首先知道的一点，不能将数字直接Integer.parseInt()成整数，相加，然后再转为二进制的string，这样会溢出。当然，你可以借用BigInteger(value, radix)这样的现成的类，不过就失去了本题的意义。这个链接里有一个这样的解法。
https://oj.leetcode.com/discuss/20559/java-one-line-solution-using-biginteger
我们考虑一般的解法。一个游标，从a和b的最后一位往前遍历，同位转化为int相加，这个结果还要加上前面一位的进位extra。这个值%2就是该位的值，/2是进位的值。如此往复，直到首先到达a或b的开头，即较短的那个。
然后把多出的一段拿出来，加上extra，接在上面结果的前面，就可以了。这时一个递归的调用。递归结束的条件是，addBinary(String a, String b)，这里a和b的长度相等。可能是一开始就相等，也可能是a多出来一段，这时b.length()==0，那么也就是extra往前递归一直加到a.length()也是0，也就是a递归加结束了。
最后不要忘记如果extra还有1，一定要加上去。0就不要加了。
public class Solution { public String addBinary(String a, String b) { int minLength = Math.min(a.length(), b.length()); String result = ""; //记录进位 int extra = 0; //a和b的index要从后向前加 for(int i = 0; i < minLength; i++){ int sum = ((a.charAt(a.length() - 1 - i) - ‘0‘) + (b.charAt(b.length() - 1 - i) - ‘0‘) + extra) % 2; result = String.valueOf(sum) + result; extra = ((a.charAt(a.length() - 1 - i) - ‘0‘) + (b.charAt(b.length() - 1 - i) - ‘0‘) + extra) / 2; } //进位加上a或b较长的前面的一段 if(a.length() < b.length()){ result = addBinary(b.substring(0, b.length() - a.length()), String.valueOf(extra)) + result; }else if(a.length() > b.length()){ result = addBinary(a.substring(0, a.length() - b.length()), String.valueOf(extra)) + result; }else{ //a和b长度相等，也可能是上面递归调用到第一位，加上进位，如果进位为0不加，否则就会出现01111这样的情况 if(extra == 1){ result = String.valueOf(extra) + result; } } return result; } }
上面是一个AC的递归解法。这道题还用了递归，实在是不应该，想想一定有普通的循环，线性的解法。
为什么循环一定要到a与b较短的那个就结束了？怕越界。为什么怕越界？越界不就是在较短的那个字符串前面加上n个0吗？思路一下子出来，这样循环终止的条件就是a和b中较长的长度了。而且可以以一个思路直接循环到结束。代码如下。
public class Solution { public String addBinary(String a, String b) { int maxLength = Math.max(a.length(), b.length()); String result = ""; //记录进位 int extra = 0; //a和b的index要从后向前加 for(int i = 0; i < maxLength; i++){ char aChar = ‘0‘; char bChar = ‘0‘; if(a.length() - 1 - i >= 0){ aChar = a.charAt(a.length() - 1 - i); } if(b.length() - 1 - i >= 0){ bChar = b.charAt(b.length() - 1 - i); } int sum = ((aChar - ‘0‘) + (bChar - ‘0‘) + extra) % 2; result = String.valueOf(sum) + result; extra = ((aChar - ‘0‘) + (bChar - ‘0‘) + extra) / 2; } if(extra == 1){ result = String.valueOf(extra) + result; } return result; } }
原文：http://www.cnblogs.com/NickyYe/p/4298922.html