## Sum of two binary strings (Add Binary)

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;
}
}
}

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;
}

}
};

__ATA.cmd.push(function() {
__ATA.initVideoSlot('atatags-370373-5e29ba54367af', {
sectionId: '370373',
});
});

__ATA.cmd.push(function() {
__ATA.initDynamicSlot({
id: 'atatags-26942-5e29ba54367d7',
location: 120,
formFactor: '001',
label: {
},
creative: {
},
privacySettings: {
text: 'Privacy settings',
}
}
});
});

Related
```

1. Gui
Jul 20, 2012 @ 04:23:29

In 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:31

Notice 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.

2. Ali
Oct 16, 2012 @ 02:29:42

But you aren’t stopping the loop right ? like checking if theres no carry then breaking the recursion

• Runhe Tian
Oct 16, 2012 @ 23:12:51

The base step is at line 3. When there is no ‘1’ in b, meaning that there is no carries any more.