【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,如何在不使用+和-运算符的情况下,算出a和b的和?

分析:
operator+用不了,再往底层想,二进制是如何处理加法的呢?我们先看下面的二进制相加的例子:1001+1010=10011(等价于十进制下的9+10=19)
(1)不考虑进位:1+0=1, 0+1=1, 0+0=0, 1+1=0 —>1^0=1, 0^1=1, 0^0=0, 1^1=0。即不考虑进位的情况下,加法操作关联于异或操作。
因此,不考虑进位,上述二进制相加的结果为:0011(十进制下的3)
(2)只考虑进位:1+0=0, 0+1=0, 0+0=0, 1+1=1—>1&0=0, 0&1=0, 0&0=0, 1&1=1。即只考虑进位的情况下,加法操作关联于位与操作再左移一位。
因此,只考虑进位,上述二进制相加再向左移动一位结果为:10000(十进制下的16)
(3)将两个结果相加:0011+10000=10011(十进制下的19)。

再分析,十进制下也是这种情况吗?12+28=40
(1)不考虑进位:可得:30
(2)只考虑进位:可得:10
(3)最终结果:30+10=40

由上面的分析,可知,加法运算其实就是异或运算位与运算的结合,一直递归,直到没有进位(即只考虑进位的情况下,是000…时),这时与0求异或就是其本身(说明递归到了临界点)。return结果即可。

上述函数体,可以用一个三元运算符简化成一行代码:

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注