問題描述

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

分析

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

解題思路

（1）二進(jìn)制加法與十進(jìn)制加法類似，從低位開始加和，直到高位，但在加和過程中需要考慮低位數(shù)加和的進(jìn)位。假設(shè)兩個二進(jìn)制數(shù)分別為a1,b1，低位的進(jìn)位為c1，加法和為s，進(jìn)位為c則：
%2)
/2)
（2）二進(jìn)制加法同時還需要考慮最高位的進(jìn)位情況，若最高位進(jìn)位不為零，則和的位數(shù)比兩個加數(shù)中的位數(shù)最多的多一位。

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

代碼

char* addBinary(char* a, char* b) {
    int size,size1,size2,i,j;
    int carr=0;                                    //進(jìn)位
    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                                       //若本字符串長度小于最長字符串，則高位補(bǔ)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;                  //進(jìn)位
        
        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)                                     //高位有進(jìn)位
    {
        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;
}

參考文獻(xiàn)

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