【题目】

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

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

【题意】

给定两个二进制字符串，返回它们的和（也是一个二进制字符串）。

【分析】

类似大数加法

【代码】

/*********************************
*   日期：2014-02-05
*   作者：SJF0115
*   题号: Add Binary
*   来源：http://oj.leetcode.com/problems/add-binary/
*   结果：AC
*   来源：LeetCode
*   总结：
**********************************/
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;


class Solution {
public:
    string addBinary(string a, string b) {
        int lenA = a.length();
        int lenB = b.length();
        if(lenA == 0){
            return b;
        }
        else if(lenB == 0){
            return a;
        }
        int max = lenA > lenB ? (lenA + 2) : (lenB + 2);
        char* result = new char[max];
        int index = 0;
        int i = lenA-1,j = lenB-1;
        int numA,numB,c = 0,sum = 0;
        //加法
        while(i >= 0 || j >= 0){
            numA = i >= 0 ? (a[i] - ‘0‘) : 0;
            numB = j >= 0 ? (b[j] - ‘0‘) : 0;
            sum = numA + numB + c;
            c = sum / 2;
            result[index++] = sum % 2 + ‘0‘;
            i--;
            j--;
        }
        //最后一个进位
        if(c > 0){
            result[index++] = c + ‘0‘;
        }
        result[index] = ‘\0‘;
        //反转
        for(i = 0,j = index - 1;i < j;i++,j--){
            char temp = result[i];
            result[i] = result[j];
            result[j] = temp;
        }
        return string(result);
    }
};

int main() {
    Solution solution;
    string a = "1010";
    string b = "1011";
    string str = solution.addBinary(a,b);
    cout<<str<<endl;
    return 0;
}

【代码2】

class Solution {
public:
    string addBinary(string a, string b) {
        int lenA = a.length();
        int lenB = b.length();
        if(lenA == 0){
            return b;
        }
        else if(lenB == 0){
            return a;
        }
        string result;
        int index = 0;
        int i = lenA-1,j = lenB-1;
        int numA,numB,c = 0,sum = 0;
        //加法
        while(i >= 0 || j >= 0 || c > 0){
            numA = i >= 0 ? (a[i] - ‘0‘) : 0;
            numB = j >= 0 ? (b[j] - ‘0‘) : 0;
            sum = numA + numB + c;
            c = sum / 2;
            result.insert(result.begin(),sum % 2 + ‘0‘);
            i--;
            j--;
        }
        return result;
    }
};

【代码3】

class Solution {
public:
    string addBinary(string a, string b) {
        int lenA = a.length();
        int lenB = b.length();
        string result;
        int index = 0;
        int i = lenA-1,j = lenB-1;
        int sum = 0;
        //加法
        while(i >= 0 || j >= 0){
            sum += i >= 0 ? (a[i] - ‘0‘) : 0;
            sum += j >= 0 ? (b[j] - ‘0‘) : 0;
            result = ((sum & 1) ? "1" : "0") + result;
            sum >>= 1;
            i--;
            j--;
        }
        return sum ? "1" + result : result;
    }
};

LeetCode之Add Binary