371. 两整数之和

发表于 分类于 阅读次数： Waline： 本文字数： 155 阅读时长 ≈ 1 分钟

考点

  • 异或技巧

题解

1
2
3
4
5
6
7
8
9
10
11
class Solution {
	public:
		int getSum(unsigned int carry, int sum) {
			while (carry) {
				int tmp = sum;
				sum = carry ^ tmp;
				carry = (carry & tmp) << 1;
			}
			return sum;
		}
};

时间复杂度：存在异议，但个人认为不会超过32次

空间复杂度：\(O\left( 1 \right)\)

思路

记住这个位运算小技巧就好了，假设有a和b两个整数，不限正负

  • \(a\oplus b\)可得到a与b的无进位加法结果
  • \(\left( a\&b \right) <<1\)可得到a与b的加法进位

由于进位可能会溢出，比如-1 + 1这组数据；所以需用无符号类型保存进位