算法

(位运算实现) $O(\log n)$

1. 迭代实现 a + b，只能使用位运算。
2. 首先求出 a ^ b 和 (a & b) << 1，然后把这两个结果分别赋值给 a 和 b，直到 b 为 0。
3. 异或是加法的基础，进位用按位与来判断。

时间复杂度

• 每迭代一次，低位至少会减少一次进位，所以最多迭代 $O(\log n)$ 次。

C++ 代码

#include <iostream>

using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    while (b) {
        int x = a ^ b;
        int y = (a & b) << 1;
        a = x;
        b = y;
    }

    cout << a << endl;
    return 0;
}