C语言基础算法二进制求和leecode

快来打我* 2022-12-30 10:42 142阅读 0赞

## 题目： ##

**二进制求和**  
给你两个二进制字符串，返回它们的和（用二进制表示）。

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

示例 1:

输入: a = “11”, b = “1”  
输出: “100”  
示例 2:

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

提示：

每个字符串仅由字符 ‘0’ 或 ‘1’ 组成。  
1 <= a.length, b.length <= 10^4  
字符串如果不是 “0” ，就都不含前导零。

可能很多人想在转换成10进制这样去计算，但是这样想的话，计算量非常大了。既然是二进制求和，那么我们就用二进制的方法去做。本质上二进制求和还有十进制求和是一样的，我们都知道存在4个元素，俩个加数的相应位，和的值，还有进位，我们分别去判别并计算出来就好。

大师匈搞了俩种办法，一种直接位运算，一种是结合了字符和16进制值的对应关系进行转换，但是关键在于那里呢，为什么字符异或运算之后还能保持原来的值，这一些细节，需要琢磨。

char * addBinary(char * a, char * b){ 
        /* int i = strlen(a); int j = strlen(b); int len = i > j? i: j; char* res = (char*)malloc(sizeof(char) * (len + 2)); res[++len] = 0; char carry = '0'; char pa, pb; while(len > 1 || carry == '1') { pa = i > 0? a[--i]: '0'; pb = j > 0? b[--j]: '0'; res[--len] = pa ^ pb ^ carry; carry = (pa & carry) | (pb & carry) | (pa & pb); } return res + len; */
    
        static char buf[128];
        char *p = buf+127;
        *p = '\0';
        
        int la = strlen(a), lb = strlen(b), carry = 0;
    
        while (la || lb || carry) { 
            if (la) { 
                carry += a[--la]&1;
            }   
            if (lb) { 
                carry += b[--lb]&1;
            }   
    
            *--p = carry & 1 | 0x30;
            carry = carry >> 1;
        }
        return p;
    }

题目虽简单，但是需要灵活的思维和扎实的基础，共勉，加油。。。。