不使用加法运算符求和

题目

不使用加法运算符,求两数之和,原题链接http://www.lintcode.com/zh-cn/problem/a-b-problem/

分析

不允许使用加法运算符,也就是不允许使用四则运算符,否则可以转换为减法, a + b == a - (-b) 。禁用四则运算符后,就只能依赖位运算了。

单靠位运算能进行四则运算么?当然可以!CPU中的重要部件算术逻辑单元ALU就是通过位运算实现的数学计算。只要能实现加法,四则运算就都可以实现,因为四则运算最终可以归结加法运算,减法是加法的逆运算,乘法就是加法的,除法是乘法的逆运算。

位运算加法

先考虑最简单的加法情况,即不包含进位,这里讲的进位是二进制状态下的进位,比如二进制数100+010=110这种情况。

    100
+   010
--------
    110

可以发现,如果没有任何进位的情况下,两个二进制数相加,只有1+0和0+0两种情况,1+0=>1,0+0=>0,这恰好与位运算异或(XOR)的运算规则一致!此时 A + B = A XOR B

如果两个二进制数相加,有进位的话又回如何呢?假设两个二进制数分别为1010和1111

    1010
+   1111
---------
   10001

会产生进位的地方,只有同等位上的值同时为1,显然,通过逻辑与运算,就可以得知产生进位的二进制位。


1010
& 1111

1010
进位会加到高一位的位置上,此时,问题就又回归成“计算两数的和”!

再完整的回顾一下,位运算相加的过程:

  • 先不考虑进位,A XOR B获得无进位的运算结果
  • 通过A AND B计算出进位的值
  • 如果有进位,将进位部分左移一位(向高位进位)
  • A+B的问题,此时变成了 (A OXR B) + (A & B)的问题,迭代计算

代码实现


int aplusb(int a, int b) {
        int xor = a ^ b;
        int i = a & b;
        return i == 0 ? i : aplusb(xor, i<<1);
}

Show Comments

Get the latest posts delivered right to your inbox.