二进制求和

题意

以字符串形式给两个二进制数字，求它们的二进制表示下的和

方法

python3内置高精度库

分析

注意到数字长度很大，因此普通的int/long等是无法满足，需要高精度

而python3的自带高精度，考虑使用python3内置的高精度

代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param A string字符串 
# @param B string字符串 
# @return string字符串
#
class Solution:
    def binaryAdd(self , A: str, B: str) -> str:
        return format(int(A,2)+int(B,2),"b")

复杂度分析

空间复杂度: 主要在数字和字符串转换上，空间复杂度为$O(n)O(n)$

时间复杂度: 主要在数字和字符串转换以及加法运算上，所以总时间复杂度为$O(n)O(n)$

模拟高精度加法

分析

加法，小学学过竖式加法，分别需要

1. 末位对齐
2. 加和值与进位
3. 大于进制就进位

所以我们模拟它，用一个额外变量记录进位

每一位的结果 = A的当前位 + B的当前位 + 进位的值

进位 = 计算结果 ÷ 进制

样例

以样例数据为例

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param A string字符串 
     * @param B string字符串 
     * @return string字符串
     */
    string binaryAdd(string A, string B) {
        string r = "";
        int digit = 0;// 进位
        for(int i = 0; i < max(A.length(),B.length()); i++){
            if(i < A.length())digit += A[A.length()-1-i] - '0'; // A的低i位
            if(i < B.length())digit += B[B.length()-1-i] - '0'; // B的低i位
            r = string("") + char(digit%2 + '0') + r; // 拼接结果
            digit /= 2; // 进位
        }
        while(digit){ // 超出了原本的位数
            r = string("") + char(digit%2 + '0') + r; // 拼接结果
            digit /=2; // 进位
        }
        return r;
    }
};

复杂度分析

空间复杂度: 主要消耗在记录结果上，空间复杂度为$O(n)O(n)$

时间复杂度: 对于每位运算代价为常数，所以总时间复杂度为$O(n)O(n)$