题目：

Given two binary strings, return their sum (also a binary string).

For example,

a = "11"

b = "1"

Return "100".

 

题解：

二进制加法都是从最低位（从右加到左）。所以对两个字符串要从最后一位开始加，如果遇见长度不一的情况，就把短的字符串高位补0.

每轮计算要加上进位，最后跳出循环后要坚持进位是否为1，以便更新结果。

 

代码如下（from discussion）：

 

 1 

public String addBinary(String a, String b) {

 2     

int m = a.length();

 3     

int n = b.length();

 4     

int carry = 0;

 5     String res = "";

 6     

//

 the final length of the result depends on the bigger length between a and b, 

 7 

    

//

 (also the value of carry, if carry = 1, add "1" at the head of result, otherwise)

 8 

    

int maxLen = Math.max(m, n);

 9     

for (

int i = 0; i < maxLen; i++) {

10         

//

 start from last char of a and b

11 

        

//

 notice that left side is int and right side is char

12 

        

//

 so we need to  minus the decimal value of '0'

13 

        

int p=0,q=0;

14         

if(i<m)

15             p = a.charAt(m-1-i) - '0';

16         

else

17             p = 0;

18         

19         

if(i<n)

20             q = b.charAt(n-1-i)-'0';

21         

else

22             q = 0;

23             

24         

int tmp = p + q + carry;

25         carry = tmp / 2;

26         res += tmp % 2;

27     }

28     

return (carry == 0) ? res : "1" + res;

29     }