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

For example,

a = "11"

b = "1"

Return "100".

Analyse: Using XOR(^) to compute the result of the bit-add and line 22 to reserve the carry bit. Be cautious about the last carry.

1 class Solution { 2 public: 3     string addBinary(string a, string b) { 4         int carry = 0; 5         string result; 6         for(int i = a.length() - 1, j = b.length() - 1; i >= 0 || j >= 0; i--, j--){ 7             int sa, sb; 8             if(i < 0) { 9                 sa = 0; 10                 sb = b[j] - '0';11             }12             else if(j < 0){13                 sb = 0; 14                 sa = a[i] - '0';15             }16             else{17                 sa = a[i] - '0';18                 sb = b[j] - '0';19             }20             char current = sa ^ sb ^ carry + '0';21             result = current + result;22             if((carry + sa + sb) / 2) carry = 1;23             else carry = 0;24         }25         if(carry) result = '1' + result;26         return result;27     }28 };