問題描述

Given two binary strings, return their sum (also a binary string).
For example,
a = "11"
b = "1"
Return "100".

分析

題目要求完成兩個二進制的加法艾岂，加數(shù)與被加數(shù)分別來源于兩個字符串馒过，最終加和結(jié)果以二進制字符串形式返回。

解題思路

（1）二進制加法與十進制加法類似悦陋，從低位開始加和贱田，直到高位忌栅，但在加和過程中需要考慮低位數(shù)加和的進位沸手。假設兩個二進制數(shù)分別為a1,b1锄贼，低位的進位為c1票灰，加法和為s，進位為c則：
%2)
/2)
（2）二進制加法同時還需要考慮最高位的進位情況咱娶，若最高位進位不為零米间，則和的位數(shù)比兩個加數(shù)中的位數(shù)最多的多一位。

（2）若兩個數(shù)位數(shù)不同膘侮，則對較短的數(shù)高位補零使其位數(shù)相同屈糊。

代碼

char* addBinary(char* a, char* b) {
    int size,size1,size2,i,j;
    int carr=0;                                    //進位
    size1=strlen(a);                               //字符串長度
    size2=strlen(b);
    size=size1;
    char *result;                                  //加和返回結(jié)果
    if(size2>size1)
        size=size2;                                //最長字符串長度
    int a1[size];
    int b1[size];                                  //存放兩個加數(shù)
    int c1[size+1];
    for (i=0;i<size;i++)
    {   
        if(size1-i-1>=0)
            a1[i]=a[size1-i-1]-'0';                //將字符串轉(zhuǎn)換為整型，低位在前琼了，高位在后
        else                                       //若本字符串長度小于最長字符串逻锐，則高位補0；
            a1[i]=0;                 
        
        if(size2-i-1>=0)
            b1[i]=b[size2-i-1]-'0';
        else
            b1[i]=0;
    
        c1[i]=(a1[i]+b1[i]+carr)%2;                 //加和
        carr=(a1[i]+b1[i]+carr)/2;                  //進位
        
        printf("a[%d]=%d\n",i,a1[i]);
        printf("b1[%d]=%d\n",i,b1[i]);
        printf("c1[%d]=%d\n",i,c1[i]);
        printf("carr=%d\n",carr);
        
    }
    if(carr==1)                                     //高位有進位
    {
        c1[size]=carr;
        size=size+1;
    }

    result = (char* )malloc(sizeof(char)*(size+1));
    for (j=0;j<size;j++)
    {
        result[j]=c1[size-j-1]+'0';
        printf("%c\n",result[j]);
    }
    result[size]='\0';
    printf("%s",result);
    return result;
}

參考文獻

[1] http://blog.csdn.net/ojshilu/article/details/19638333
[2] http://www.cnblogs.com/kiven-code/archive/2012/09/15/2686922.html