博客

Leetcode67. 二进制求和（C语言）

算法-数学（字符串加减法）：

算法与数据结构参考

题目：


给定两个二进制字符串，返回他们的和（用二进制表示）。

输入为非空字符串且只包含数字 1 和 0。例:


输入: a = “1010”, b = “1011”

输出: “10101”

思路：


双指针分别遍历两个字符串，

注意char和int转换

。

代码：

char* addBinary(char* a, char* b) {
    int lena = strlen(a);
    int lenb = strlen(b);
    
    int len = lena > lenb? lena: lenb;
    char* res = (char*)malloc(sizeof(char) * (len + 2));	//+2防进位
    res[++len] = 0;
    
    char carry = '0';
    char pa, pb;
    while(len > 1 || carry == '1') {
        pa = lena > 0? a[--lena]: '0';
        pb = lenb > 0? b[--lenb]: '0';						//处理长度不一的情况
        
        res[--len] = pa ^ pb ^ carry; 						// 当前位
        carry = (pa & carry) | (pb & carry) | (pa & pb); 	//进位
    }
    
    return res + len;										//返回 res 的第 len 到末尾的字符
}
//参考评论区@银河也是河