Given two binary strings, return their sum (also a binary string).
For example,
a = "11"
b = "1"
Return "100".
給出兩個(gè)表示二進(jìn)制的字符串，求相加后的結(jié)果，字符串形式返回。
考慮到二進(jìn)制相加進(jìn)位最大為1，相加結(jié)果最大是11胜榔，對(duì)2取余是當(dāng)前位的值，除以2可以得到進(jìn)位的值品山。用兩個(gè)指針?lè)謩e指向兩個(gè)字符串末尾友酱，依次計(jì)算每位的值以及是否產(chǎn)生進(jìn)位。
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中的答案和自己思路是一樣的刑顺，但是在處理每一位相加的時(shí)候氯窍，只需要分別判斷i和j是否越界。每次操作StringBuilder時(shí)也不需要每次指明insert到0位置蹲堂，只需要最后reverse即可狼讨。進(jìn)位的命名一般用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();
}