A+B问题

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

前言

萌新重新开始刷题了, 在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;