使用位操作（XOR 和 AND）执行二进制加法的运行时间是多少？

Question

显然你可以通过位操作来执行二进制加法。这是它的Python代码：

class Solution:
    def addBinary(self, a, b) -> str:
        x, y = int(a, 2), int(b, 2)
        while y:
            answer = x ^ y
            carry = (x & y) << 1
            x, y = answer, carry
        return bin(x)[2:]

基本上所做的是将二进制字符串转换为以 10 为基数形式的整数。然后对两个数字进行异或。 XOR 是不考虑进位的总和。然后通过对 x 和 y 进行 AND 运算来分别计算进位。在下一轮迭代中，求出进位与上一个和的和，并以同样的方式求出本次的进位，直到没有进位为止。

我很难解释 while 循环的运行时间。显然它是 O(max(N,M))，其中 N 表示 a 中的位数，M 是 b 中的位数。

但是为什么呢？不知道如何分析这里的运行时间。

Answer 1

不是 O(max(N,M)) 而是 O(max(N,M)^2)。考虑

a = '1' * N' and 'b = '1'

。您将循环 N 次，每次都会产生一个 N 位数字。