使用位操作（XOR与AND）实现二进制加法的时间复杂度分析

先贴出你提到的位操作实现二进制加法的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:]

接下来分析循环的时间复杂度为什么是O(max(N,M))，其中N、M分别是a、b的二进制位数：

我们记K = max(N,M)，也就是两个二进制数中更长的那个的位数。

核心逻辑：循环迭代次数的上限是K #

每次循环的作用是把当前的进位y和无进位和x重新计算，直到没有进位（y=0）。关键在于：

• 每次循环生成的carry是(x & y) << 1，这意味着carry中的所有1的位置，都比上一轮产生进位的位置左移了一位（也就是更高一位）。
• 最坏情况下，进位需要逐位向上传递，比如当其中一个数是K个1（如111...1），另一个数是1时：
  1. 第一次循环：进位是2（二进制10），无进位和是111...10
  2. 第二次循环：进位是4（二进制100），无进位和是111...100
     ...
     第K次循环：进位是2^K，无进位和是0，下一次循环时carry会变成0，循环结束。

这种最坏情况下，循环会执行K次，也就是O(max(N,M))次迭代。

每次循环的操作是常数时间 #

循环内的异或（^）、与（&）、左移（<<）操作，在算法分析中都被视为处理固定位数的常数时间操作（因为每次操作的位数不会超过K，而K是输入的规模）。

综上，整个循环的时间复杂度由迭代次数决定，即O(max(N,M))。

内容的提问来源于stack exchange，提问作者Shisui