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

INPUT: a = “11”, b = “1”

OUTPUT: “100”

**Thoughts:**

Think about how we do binary addition. We first align the two numbers to the right (or padding 0 to the left for small number). Here, we convert b into “01”. Then we do additions from right to left, digit by digit. We also need to take care of carries. We can actually separate these two process: we do addition first, without thinking about carries; we then only do carries. In the end we add up those two results together. As in the example, we first do the summation of a = “11” and b = “01” and we get “10”; we then do the carries, we get “01”, as the carries will be applied to the next left digit, we shift it to left for one bit, i.e., we have “010”. We know need to calculate “10” + “010”, how we can do that? Well, we just recursively go through the process described before. When do we stop? What is the base case? When there’s no carries anymore! At that time, we just return whatever the sum is. We can mimic this process using string manipulations.

**Code (Java):**

public class Solution {
public String addBinary(String a, String b) {
if(b.indexOf('1') == -1)
return a.indexOf('1') == -1 ? a : a.substring(a.indexOf('1'));
int diff = Math.abs(a.length() - b.length());
if(a.length() > b.length()) {
for(int i = 0; i < diff; ++i)
b = '0' + b;
} else {
for(int i = 0; i < diff; ++i)
a = '0' + a;
}
String sum = new String();
String carry = "0";
for(int i = a.length() - 1; i >= 0; --i) {
if( (a.charAt(i) == '1' && b.charAt(i) == '1') ||
(a.charAt(i) == '0' && b.charAt(i) == '0'))
sum = '0' + sum;
else
sum = '1' + sum;
if (a.charAt(i) == '1' && b.charAt(i) == '1')
carry = '1' + carry;
else
carry = '0' + carry;
}
return addBinary(sum, carry);
}
}

**Code (C++):**

class Solution {
public:
string addBinary(string a, string b) {
if(b.find_first_of('1') == string::npos)
return a.find_first_of('1') == string::npos ?
a : a.substr(a.find_first_of('1'));
int diff = abs((int)a.size() - (int)b.size());
if(a.size() > b.size()) {
for(int i = 0; i < diff; ++i)
b = '0' + b;
} else {
for(int i = 0; i < diff; ++i)
a = '0' + a;
}
string sum;
string carry = "0";
for(int i = a.size() - 1; i >= 0; --i) {
if( (a.at(i) == '1' && b.at(i) == '1') ||
(a.at(i) == '0' && b.at(i) == '0'))
sum = '0' + sum;
else
sum = '1' + sum;
if (a.at(i) == '1' && b.at(i) == '1')
carry = '1' + carry;
else
carry = '0' + carry;
}
return addBinary(sum, carry);
}
};

### Like this:

Like Loading...

*Related*

Gui

Jul 20, 2012@ 04:23:29In you Java code, at line 10 and 12, that says b = ‘0’ + b. I think there is a flaw, you know, in Java, String object can not be modify directly in this way. Right?

Runhe Tian

Jul 20, 2012@ 11:52:31Notice that I don’t modify b in any way. Java evaluate the expression ‘0’+b into a constant string then assign the reference of that string to b.

Ali

Oct 16, 2012@ 02:29:42But you aren’t stopping the loop right ? like checking if theres no carry then breaking the recursion

Runhe Tian

Oct 16, 2012@ 23:12:51The base step is at line 3. When there is no ‘1’ in b, meaning that there is no carries any more.