[leetcode] Add Binary


Add Binary

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

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

二进制加法,注意进位。和字符串访问时的末尾对齐。

class Solution {
public:
    string addBinary(string a, string b) {
        if(a.empty())
            return b;
        else if(b.empty())
            return a;
        int carry = 0;
        string sum;
        int i = 0;
        int aLen = a.size() - 1;
        int bLen = b.size() - 1;
        while(aLen - i >= 0 && bLen - i >= 0){
            int digit = carry + a[aLen - i] - '0' + b[bLen - i] - '0';
            if(digit > 1){
                carry = 1;
                digit -= 2;
            }
            else{
                carry = 0;
            }
            sum.insert(sum.begin(), digit + '0');
            i++;
        }
        //a is longer than b
        while(aLen - i >= 0){
            int digit = carry + a[aLen - i] - '0';
            if(digit > 1){
                carry = 1;
                digit -= 2;
            }
            else{
                carry = 0;
            }
            sum.insert(sum.begin(), digit + '0');
            i++;
        }
        //b is longer than a
        while(bLen - i >= 0){
            int digit = carry + b[bLen - i] - '0';
            if(digit > 1){
                carry = 1;
                digit -= 2;
            }
            else{
                carry = 0;
            }
            sum.insert(sum.begin(), digit + '0');
            i++;
        }
        if(carry == 1){
            sum.insert(sum.begin(), '1');
            carry = 0;
        }
        return sum;
    }
};

 

Untitled

Leave a comment

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.