Leetcode: Add binary (detailed description)

PROBLEM:

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

For example,
a = "11"
b = "1"
Return "100".

Hide Tags

 Math String

Show Similar Problems

Analysis:

see the second method for simpler resolution.



This is a really good problem for you to practice the string class and the coding ability. It takes me a whole morning to do it. But in the end I found it really worth the efforts. I highly recommend you to finish this one in patience!!
1. Understand the problem correctly at first!

As shown in the figure above, before addition, the two strings should be lined in the right side. And note that the bits in the right is the lower bits while the bits one left is the higher bits (Initially, I didn't understand this and waste me lots of time).

2. How to fetch the last bits for both a and b to do the addition, especially when the length of a and b are different?
One way is to reverse the order for both a and b, and then we can fetch the bits out with a normal order.
Anther smarter way is to use pointers to fetch the bit from right to left. Or simply using two references:

for(int i = a.size()-1, j = b.size()-1; i >=0 || j>=0; --i,--j){}

3. string and integers conversion. Bits are char type, but we need to do addition (usually we do summation in int domain) and then return them as char.
First way is to do the addition directly as char is also represented as int numbers in ASC Code.

int m = '0' + '1';//so m=48+49=97.

 But NOTE that, the char is represented as int whose range is -127~+127, so if do the following:

int m = '0' + '1' + '1';//so m=48+49+49= -126, it's negative!!

 So to prevent negative value, we should define m as unsigned like:

unsigned m = '0' + '1' + '1';//so m=48+49+49= 145, it's positive now!!

Another way is to use -'0' to do the conversion between int and char:

char m='0', n='1';

int mm =m-'0', nn=n-'0'; //now mm =0 and n=1 in int domain

////////////////////////////////////////////////////////
//codes

class Solution {

public:

       string addBinary(string a, string b) {

              string::iterator ai = a.end() - 1;

              string::iterator bi = b.end() - 1;

              int leng = a.size() >= b.size() ? a.size() : b.size();

              char a_c = '0', b_c = '0', c = '0', sum = '0';

              int count = 0;

              unsigned utmp=0;

              string result;// = { "0" };

              //resize to size of 'leng+1'. +1 is for the final potential remaining carrier

              result.resize(leng+1, '0');

              for (int i = leng-1; i>-1; i--){

                     //fetch a bit

                     a_c = count<a.size() ? *ai : '0';

                     b_c = count<b.size() ? *bi : '0';

                     utmp = a_c + b_c + c;

                     //carrier c. In ASC, '0'=48, maximal is 127 for ASC

                     cout << (3 * '0' + 1);

                     c = utmp>(3*'0'+1)?'1':'0';

                     //value for store

                     sum = (utmp == 3 * '0' || utmp == 3 * '0' + 2) ? '0' : '1';

                     result[i + 1] = sum;

                     count++;

                     //adress change. Adress overflow should be prevented!!

                     ai = ai == a.begin() ? ai : --ai;

                     bi = bi == b.begin() ? bi : --bi;

              }

              if (c == '1'){

                     result[0] = '1';

              }

              //otherwise remove the first item

              else{

                     result.erase(result.begin());

              }

              return result;

       }

};




revised code:

Two ways to insert a char into a string, see the codes below:

class Solution {
public:
    string addBinary(string a, string b) {
        string res;
        int i=a.length()-1, j=b.length()-1, c=0;
        while(i>=0 || j>=0){
            int tmp=(i>=0?a[i]-'0':0)+(j>=0?b[j]-'0':0)+c;
            string sum=(tmp==0||tmp==2)?"0":"1";
            c=(tmp>=2)?1:0;
            res.insert(0, sum); //Way one: to insert a char into a string "1", set the char into a string'1'->"1"
            i--;
            j--;
         
        }
        if(c==1)res.insert(0,1,'1'); // Way two: to insert a char into a string, string& insert(size_type pos, size_type n, char c);
        return res;
    }
 
};