LeetCode-67. Add Binary

问题描述

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

分析

题目要求完成两个二进制的加法，加数与被加数分别来源于两个字符串，最终加和结果以二进制字符串形式返回。

解题思路

（1）二进制加法与十进制加法类似，从低位开始加和，直到高位，但在加和过程中需要考虑低位数加和的进位。假设两个二进制数分别为a1,b1，低位的进位为c1，加法和为s，进位为c则：
%2)
/2)
（2）二进制加法同时还需要考虑最高位的进位情况，若最高位进位不为零，则和的位数比两个加数中的位数最多的多一位。

（2）若两个数位数不同，则对较短的数高位补零使其位数相同。

代码

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;                                  //加和返回结果
    if(size2>size1)
        size=size2;                                //最长字符串长度
    int a1[size];
    int b1[size];                                  //存放两个加数
    int c1[size+1];
    for (i=0;i<size;i++)
    {   
        if(size1-i-1>=0)
            a1[i]=a[size1-i-1]-'0';                //将字符串转换为整型，低位在前，高位在后
        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