A+B问题

前言

萌新重新开始刷题了, 在LintCode遇到一道题目, 是讲不用+运算符进行加法运算。
A + B 问题

不进位加法算法

既然不用+运算符, 那就直接return a-(-b)就行啦~

言归正传, 既然不能用+运算符, 那必然是位运算的范畴了。

异或运算, 又叫做不进位加法, 这里的加法都是基于二进制的。

0 1
0 0+0=0 0+1=1
1 1+0=1 1+1=0(不进位)

再来看下异或运算

0 1
0 0^0=0 0^1=1
1 1^0=1 1^1=0

可以看出 不进位加法 = 异或运算

进位算法

进位的情况只有一种, 也就是1+1的情况, 可以通过&与运算找到。
也就是说, 我们需要找到全1的一位, 再左移一位, 就可以得到进位后的值。

下面是一个加法的例子

1
2
3
4
a       + b         = (a ^ b)  + (a & b << 1)
4(0100) + 6(0110) = 2(0010) + 4(0100) << 1
4(0100) + 6(0110) = 2(0010) + 8(1000)
2(0010) + 8(1000) = 10(1010) + 0(0000)

当不需要进位之后, 运算结束。

伪代码

1
2
3
4
5
6
do {
int xor=a^b, and=(a&b)<<1;
a = xor;
b = and;
} while(b != 0);
return a;