Today’s Leetcode July Challenge is another bit manipulation problem–I feel like we’ve had a few of those lately–wherein we’re asked to sum two binary numbers and asked to return their sum. The twist is that the inputs are given as strings of containing the characters ‘1’ and ‘0’, and we are to return a result in the same format.

There’s not much for me to say about this algorithm. We’ll iteratate over both strings from right to left and add the digits bitwise, keeping track of a carry value. The output digits will be pushed to the back of a string, so that needs to be reversed after summing is complete. If there’s still a bit in the carry value after the strings are added, we just need to add a 1 bit to the front of the return value. Here’s a couple of example cases.

Input: "1010", "101"
Output: "1111"

Input: "111", "1"
Output: "1000"

And here’s my code for an algorithm with O(max(m,n)) complexity:

string addBinary(string a, string b) {
   string binarySum = "";
   int carry = 0;
   for(int i=a.length()-1, j=b.length()-1; i>=0 || j>=0; i--, j--) {
	  int aBit = (i >= 0 && a[i]=='1');
	  int bBit = (j >= 0 && b[j]=='1');
	  binarySum += to_string((aBit + bBit + carry) & 1);
	  carry = (aBit + bBit + carry) >> 1;
   }
   reverse(binarySum.begin(), binarySum.end());
   return carry ? '1' + binarySum : binarySum;
}