The idea is to add the two binary numbers (represented as strings) from back to forth bit by bit and store the result in the longer string. After the shorter string has been added, we continue to handle the carry bit. We may need to append the carry bit to the beginning of the longer string if necessary.
The code is as follows.
1 class Solution { 2 public: 3 string addBinary(string a, string b) { 4 int m = a.length(), n = b.length(), c = 0, i, j; 5 if (m < n) return addBinary(b, a); 6 for (i = m - 1, j = n - 1; j >= 0; i--, j--) { 7 int ad = a[i] - '0', bd = b[j] - '0'; 8 a[i] = (ad ^ bd ^ c) + '0'; 9 c = (ad + bd + c >= 2); 10 } 11 for (; i >= 0; i--) { 12 int ad = a[i] - '0'; 13 a[i] = (ad ^ c) + '0'; 14 c = (ad + c >= 2); 15 } 16 if (c) a = '1' + a; 17 return a; 18 } 19 };
Running the above code on the simple example a = "1", b = "11" will help you get all its details (both the two for loops and the two if statements will be hit) :-)
