LC 67. Add Binary

it is very similar to the previous add 1. But the number has become binary and is stored in sting.

First we add the two string till one become empty. Then we just append the remaining longer string (with the carry)

Also need to mind carry.

Use % to shorten the code

Binary addition will yield one if the sum of adders is odd.

    string addBinary(string a, string b) {
        int aPos = a.size() - 1;
        int bPos = b.size() - 1;
        int carry = 0;
        int newDigit = 0;
        std::string s = "";
        while (aPos >= 0 and bPos >= 0){
            newDigit = (int(a[aPos]) - '0' + int(b[bPos]) - '0' + carry) % 2;

            carry = (((int(a[aPos]) - '0'+ int(b[bPos]) + carry) - '0' > 1 )? 1:0);

            s.insert(0, std::to_string(newDigit));
            aPos --;
            bPos --;

        }

        int index = ((aPos >= 0)? aPos: bPos);
        string curS = ((aPos >= 0)? a : b);
        while (index >= 0){

            if ((int(curS[index]) - '0' + carry) % 2){
                newDigit = 1;
            }
            else{
                newDigit = 0;
            }
            carry = ((int(curS[index]) - '0'+ carry > 1)? 1 : 0);
            s.insert(0, to_string(newDigit));
            index --;
        }

        if (carry)
            s.insert(0, "1");
        return s;
    }

Convert char to int

I spent a long time to debug this code; Because I forgot that casting a char to int will get the ASCII in c++!!!
to get the actual number. We subtract ‘0’ from the casted.

Some other people make it even shorter

string addBinary(string a, string b) {
        string result = "";
        int apos = a.size() - 1;
        int bpos = b.size() - 1;
        int adigit, bdigit, carry = 0;

        while (apos >= 0 || bpos >= 0 || carry == 1)
        {
            adigit = bdigit = 0;

            if (apos >= 0) adigit = a[apos] == '1';
            if (bpos >= 0) bdigit = b[bpos] == '1';
            apos --;
            bpos --;

            result = static_cast<char>(adigit ^ bdigit ^ carry + '0') + result; 
            carry = adigit + bdigit + carry >= 2;
        }

        return result;
    }

That person didn’t use casting to figure out the current digit. Instead, an digits are assumed to be 0 and turned to 1 if a[apos] == ‘1’.

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax