算法
(位运算实现) $O(\log n)$
- 迭代实现
a + b
,只能使用位运算。 - 首先求出
a ^ b
和(a & b) << 1
,然后把这两个结果分别赋值给a
和b
,直到b
为 0。 - 异或是加法的基础,进位用按位与来判断。
时间复杂度
- 每迭代一次,低位至少会减少一次进位,所以最多迭代 $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;
}
tql orz orz orz
%%%%wzc
前排!!