67. 二进制求和(C, Python)

1. 题目描述

难度：简单

2. 题目分析

• 转换法(Python)
  转换法是最容易想到的方法， 想将二个字符串转化为整型，然后将二者相加，在转化为字符串输出结果。这种方法对于Python来讲是比较容易实现的，所以推荐用Python来实现，但是对于C来讲是很麻烦的，其中涉及到了字符转二进制，二进制相加，二进制转字符串等。
• 字符串相加法（C）
  对于C语言来说，直接用字符串位对位相加即可，根据进位标志位来判断是否进位。因为字符串是二进制，所以只有‘1’和‘0’两种情况，实现起来比较容易。

在利用字符串相加法的过程，有遇到一个问题，就是在申请字符串内存空间的时候，容易报错，这是由于strlen()和sizeof()函数对于求字符串长度不同导致的：

C语言中没有字符串，用的是字符数组来模拟字符串。C风格的字符串时字符数组然后在末尾加‘/0’表示结尾。在C语言中有strlen和sizeof两个函数求字符数组的长度函数，他们俩的区别就是是否把最后的结束标志也加上去。strlen是不加的，他表示字符串的长度。而sizeof求的是字符串在内存中的长度，所以它是加上最后的’\0’的。所以一般而言后者的长度会比前者多1。

3. C语言实现

C语言实现的步骤是：

• 首先要判断两个字符串是否等长，如果不是，将短字符串前面补0到等长
• 根据进位标志位来进行字符串相加
• 判断最终结果的首位是否要进位，调整输出结果的字符串长度

源代码如下：

char * addBinary(char * a, char * b){
	// 定义的变量分别表述a的长度，b的长度，二者最长的数值，循环变量i，进位标志位flag
    int len_a, len_b, len, i,flag=0;
    // c为要输出的结果，temp为临时字符指针，new_b为更改字符串长度字后的b
    char *c, *temp,*new_b;
    len_a = strlen(a);
    len_b = strlen(b);
    int dif = abs(len_a-len_b);
    len = len_a>len_b?len_a:len_b;
    // 申请两个内存空间，c申请的空间之所以比len多2，一个是给字符串结果符预留‘/0’，一个给最后的首位进位预留，如果需要进位，那么空间长度刚好，如果不需要，要调整C的空间
    c = (char *)malloc(sizeof(char)*(len+2));
    new_b = (char *)malloc(sizeof(char)*(len+1));
    // 对申请的内存空间进行初始化，这一步很重要，缺少的话会报错
    c[0]='0';
    c[len+1]='\0';
    new_b[0]='0';
    new_b[len]='\0';
    // 判断两个字符串的长度，永远将长的字符串赋值给a，将短的字符串赋值给b,方便后续操作
    if(len_a<len_b){
        temp = a;
        a = b;
        b = temp;
    }
    // 对短字符串b进行填充补0
    for(i=0; i<len; i++){
        if(i<dif){
            new_b[i] = '0';
        }
        else{
            new_b[i] = b[i-dif];
        }
    }
    // 依次位对位进行判断，结合flag判断是否要进位
    for(i=len; i>0; i--){
        if(a[i-1] == new_b[i-1]){
            c[i] = flag==1?'1':'0';
            flag = a[i-1]=='1'?1:-1;
        }
        else{
            c[i] = flag==1?'0':'1';
        }
    }
    // 如果最后的flag=1，说明要进位，将c[0]==‘1’
    if(flag==1){
        c[0] = '1';
    }
    // 如果不需要进位，依次将c字符串向后错一位
    else{
        for(i=0; i<len+1; i++){
            c[i] = c[i+1];
        }
    }
    return c;
}

运行结果为：

4. Python实现

不得不说Python打法好：

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        return str(bin(int(a,2)+int(b,2)))[2:]

运行结果为：