二进制求和算法(leetcode第67题)

题目描述：

给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。

 

示例 1：

输入:a = "11", b = "1"
输出："100"
示例 2：

输入：a = "1010", b = "1011"
输出："10101"
 

提示：

1 <= a.length, b.length <= 104
a 和 b 仅由字符 '0' 或 '1' 组成
字符串如果不是 "0" ，就不含前导零

算法：

思路：

思路见注释

代码实现：

//进位
# include<string.h>
# include<ctype.h>
# include<stdio.h>
# include<stdlib.h>
#define MAXLEN 10010

int max(int a,int b){//取较大值
    return a>b?a:b;
}
void swap(char *a,char *b){//交换字符
    char temp=*a;
    *a=*b;
    *b=temp;
}
void reverse(char *str){//反转字符串
    int len=strlen(str);
    for(int i=0;i<len/2;i++){
        swap(&str[i],&str[len-i-1]);
    }
}
char* addBinary(char* a, char* b) {
    reverse(a),reverse(b);//反转
    int alen=strlen(a),blen=strlen(b);
    int maxlen=max(alen,blen);//分配长度要比较长长度多一-->用于进位
    char *binarySum=(char *)malloc(maxlen+2);//+2-->多留一个进位，再多留一个给结束符
    int carry=0,index=0;
    for(int k=0;k<maxlen;k++){
        //保证不越界
        carry+=k<alen?(a[k]=='1'):0;
        carry+=k<blen?(b[k]=='1'):0;
        binarySum[index++]=carry%2+'0';//取余数
        carry/=2;//取进位数
    }
    if(carry) binarySum[index++]='1';//进位判断
    binarySum[index]='\0';//结束符
    reverse(binarySum);//反转
    return binarySum;
}