Given two binary strings, return their sum (also a binary string).
For example,
a = "11"
b = "1"
Return "100".
给出两个表示二进制的字符串，求相加后的结果，字符串形式返回。
考虑到二进制相加进位最大为1，相加结果最大是11，对2取余是当前位的值，除以2可以得到进位的值。用两个指针分别指向两个字符串末尾，依次计算每位的值以及是否产生进位。
public String addBinary(String a, String b) {
if (a == null || b == null) {
return a == null ? b : a;
}
StringBuilder buff = new StringBuilder();
int alen = a.length(), blen = b.length();
int extra = 0;
for (int i = alen - 1, j = blen - 1; i >= 0 || j >= 0; i--, j--) {
int now = 0;
int cur = 0;
if (i >= 0 && j >= 0) {
now = a.charAt(i) - '0' + b.charAt(j) - '0' + extra;
} else if (i >= 0) {
now = a.charAt(i) - '0' + extra;
} else {
now = b.charAt(j) - '0' + extra;
}
cur = now % 2;
extra = now / 2;
buff.insert(0, cur);
}
if (extra > 0) {
buff.insert(0, extra);
}
return buff.toString();
}
discuss中的答案和自己思路是一样的，但是在处理每一位相加的时候，只需要分别判断i和j是否越界。每次操作StringBuilder时也不需要每次指明insert到0位置，只需要最后reverse即可。进位的命名一般用carry。
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();
}