lintCode题解 (1)

标签（空格分隔）： lintCode

---

题目: 给出两个数A,B 在不使用加法运算的符的情况下,计算 A与B的和

输入 A = 1, B = 3 ,sum = 4;

分析:这道题其实考察的就是计算机中两个数如何实现加法运算, 也就是加法器的实现原理.计算机中数字是以二进制的方式存放的.两个数使用+进行相加时,我们从二进制上看是这样的

0 0 0 1 ----1
0 0 1 1 ----3
———— + ———
0 1 0 0 ----4

这里我们看到,低位先加,如果产生进位,则高位加上低位的进位在相加.这与我们十进制相加的原理一样.

我们十进制相加时,遇十进一,二进制相加时,遇二进一,这是我们人的计算理论,然而计算机却不是这样,计算机的运算是数字逻辑电路实现的,是与,或,非门电路实现的.

对于一位二进制运算:

A   B   result
0 + 0  =  0;
1 + 1  =  0;
1 + 0  =  1;
0 + 1  =  1;

我们可以总结出这样的规律:

result = A ^ B

这个规律对于多位二进制运算基本上也是适用的;对于下面的一个例子我们看看

0 1 0 1 ----5
1 0 1 0 ----10
——— ^ ——— --- (按位做异或运算)
1 1 1 1 --- 15

但是不总是适用,对于每一位都不产生进位的情况下,我们可以得到正确的结果,那么如果产生进位呢?

0 0 1 0 1 ----5
0 1 0 1 1 ----11
——— ^ ——— ---  (按位做异或运算)
0 1 1 1 0 --- 14 (实际结果)
1 0 0 0 0 --- 16 (期望结果)

这就不对了,为什么呢?因为我们没有加上进位,如果我们加上进位就行了.

对于上面的计算进位产生在第一位(最右边),因此我们需要在第二位上加1,
于是计算的过程需要在一次做加法计算,我们使用同样的方式进行

0 1 1 1 0 --- 14 (上一步的结果)
0 0 0 1 0 --- 2(上一步的进位)
——— ^ ——— ---  (按位做异或运算)
0 1 1 0 0 --- 12 (实际结果)
1 0 0 0 0 --- 16 (期望结果)

我们发现还是不对,因为加上进位后,第二位又产生了进位,结果又不对了,我们一次在进行加上进位计算

0 1 1 0 0 --- 12(上一步的结果)
0 0 1 0 0 --- 4(上一步的进位)
——— ^ ——— ---  (按位做异或运算)
0 1 0 0 0 --- 8 (实际结果)
1 0 0 0 0 --- 16 (期望结果)

还有进位产生,再次进行运算

0 1 1 0 0 --- 8(上一步的结果)
0 1 0 0 0 --- 8(上一步的进位)
——— ^ ——— ---  (按位做异或运算)
0 0 0 0 0 --- 0 (实际结果)
1 0 0 0 0 --- 16 (期望结果)

结果产生了进位,在一次加上进位计算

0 0 0 0 0 --- 0(上一步的结果)
1 0 0 0 0 --- 16(上一步的进位)
——— ^ ——— ---(按位做异或运算)
1 0 0 0 0 --- 16 (实际结果)
1 0 0 0 0 --- 16 (期望结果)

没有进位产生了,结果也正确了.

我么发现,如果没有进位产生 sum = A ^ B这个sum就是A与B的和,如果产生了进位,则需要在其基础上加上进位,再次运算.于是问题,就转换成了判断每一次结果是否产生了进位的问题.

如何判断两个数在相加时是否有进位产生呢?

这个问题我们可以求解其对立面,我知道两个数如果相加没有进位产生,这个很简单,类似于下面

对应位上的数不会同时出现`1`
0 1 0 0 1 
1 0 1 0 0 

也就是说 A & B是等于0的,这样就可以判断这两个数没有进位产生,如果不等于0则必有进位产生.

解决了进位产生的问题,我们还需要知道进位是多少,这个问题也很简单,只要有进位产生,我们就需要将前一位加1,
于是我们不难发现进位C可以这样表示

C = (A & B) << 1;

这样我们就将问题全部分析完毕了.

写一下代码实现

long aPlusb(long a , long b){
    long sum = 0;
    long temp = a & b;
    sum = a ^ b;
   if(temp = 0){ //没有进位产生
        return sum;
   }
   //有进位产生,返回加上进位的结果
   return aPlusb(temp<<1,sum);
}