[LeetCode]371. Sum of Two Integers 计算两个整数的和

你想知道计算机是怎么完成加法运算的吗?

题目描述:

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

Example:
Given a = 1 and b = 2, return 3.

题目大意:

不使用加减法,计算两个整数a和b的和。


 

我总觉得这题不是很难。毕竟计算机的运算肯定不是用加减直接做的。它肯定有自己的一套算法。我马上去补了一下二进制位的位运算。

“(引用)

原文:来自慕课网:http://www.imooc.com/video/3650 的 00:13处。

再根据昨天所写的,0-15所有二进制数。

我发现了一件事,那就是,或运算其实已经可以完成某些数字的加法了。

比如说,6的二进制位为0110,9的二进制位为1001,6 | 9 = 1111,也就是15 。也就是说,在不进位的情况之下,其实是可以直接进行或运算完成加法运算的。

可是这远远不够。5的二进制位为0101,5 | 9 = 1101 是13,而 5 + 9 = 14,显然不对。

那么也就是说,有一个被我们俗称“进位”的步骤,要让我们通过二进制位运算来解决实现它。

……

两个小时过去了。由于基础不过关,我只能通过去尝试可能性(我想这是最笨的办法了)。最后确实完成了加法运算。

算法如下:

假定有数字a与数字b。

第1步:用新的变量c和d分别存储a与b的与运算结果和或运算结果。

c = a | b;  d = a & b;

第2步:判断 d 是否为0,若是,则 c 为所求的答案,程序结束 (此为递归或者循环的出口。);若不是,则执行第3步。

第3步:用新的变量 e 存储 c 和 d 的异或运算结果。用 f 存储 d 左移 1 位的结果。

e = c ^ d;  f = d << 1;

第4步:将 a 存储 e 的值,将 b 存储 f 的值,然后继续执行第一步。(递归或者循环)

a = e;  b = f;

窃以为这样走啊走,是肯定能到终点的。然而Leetcode竟然,竟然说我的递归可能没有出口。那行,我们用while(1)也是一点都不怂的。

最后我的答案是有经过修改的,因为要改成while(1)的循环,就减少了很多变量,变得简洁很多。

371. Sum of Two Integers

很少有一题可以想两个半小时以上的了。其实最让我难过的是这题的难度竟然是……

Easy。

没事没事,新手上路嘛。


 

之后我去网上找了一下,发现别人的思路更清晰一些。

“(引用)

原文地址:http://blog.csdn.net/qq508618087/article/details/51789576

思路: 这里用到了一个半加法的思想, 即两位单独的位相加其结果可以用异或得到, 进位可以用与得到. 然后对于两个数字来说同样可以延伸这个思想.

举个例子: 11+5, 其二进制形式为11: 1011, 5: 0101

1. 那么两个位置都为1的地方就需要进位, 所以进位值就为0001. 原位置两个数相加的结果为那个位置值的异或即1110, 即两个位置值如果不一样就为1, 一样的话要么两个位置原来值都为0结果也为0, 要么进位, 那么结果依然是0.

2. 接下来就要把进位位和下一位相加, 所以进位值左移一位,即0001变为0010, 重复上面操作可得新的进位值为0010, 原位置异或(即相加)结果为1100.

3. 继续重复上面操作直到进位为0, 可得到最终结果10000, 即16

代码如下:

总的来说,我没有什么失误吧。只是一开始得到答案,前辈是使用异或直接得出结果,而我是用或。这导致我后来要多写一步异或。在想的时候是没发现这里的重复的。感觉有点尴尬。前辈的代码更清晰,更老练。这也说明我还有很长很长很长的路要走。