两整数之和

• Sum of Two Integers

Sum of Two Integers

LeetCode 371

Given two integers a and b, return the sum of the two integers without using the operators + and -.

Example 1:

Input: a = 1, b = 2
Output: 3

Example 2:

Input: a = 2, b = 3
Output: 5

Constraints:

• -1000 <= a, b <= 1000

Approach

这道题粗看很奇怪，不使用加减法求两个整数之和。讨论区一堆神吐槽：

事实上，出题者的本意是希望大家用一种 hack 的方式来间接实现加法，只不过放着现成的加法不用，让人感觉有点舍近求远。但是如果用现成的加法，那么这道题将没任何意义。

1. 数学 对数

   我们知道，在数学上使用对数可以将两个数相乘 → 变成两个对数相加：

   \[log(a*b) = log(a) + log(b)\]

   反之，我们也可以将两个数相加转变成两个指数相乘再取对数（这里为了方便计算机实现，对数以 2 为底）：

   \[a + b = log(2^a * 2^b)\]

   当然，这样实现成本很高，还需要考虑溢出问题。

2. 计算机 位运算

   我们知道，在计算机中任何一个数都表示为二进制，我们可以考虑对两个二进制数相同部分和不同部分分开求和。 两个二进制不同部分求和使用异或即可，相同部分求和只需要与运算再乘 2。 也即：

   \[a + b = a \oplus b + 2 * (a \& b)\]

   代码：

    class Solution {
        fun getSum(a: Int, b: Int): Int {
            return a.xor(b) + a.and(b).shl(1)
        }
    }
   

   另外，位运算思路还有一个很精髓的递归写法：

    class Solution {
        tailrec fun getSum(a: Int, b: Int): Int {
            return if (b == 0) a else getSum(a.xor(b), a.and(b).shl(1))
        }
    }
   

   递归函数的 a 用来承接两个数异或运算结果，b 用来承接与运算乘2结果，当与运算为 0 时，异或运算即为最终求和。 可以证明，递归运算最终一定会收敛到 b 为 0。