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.

解法一

思路

看到这题就想到学计算机组成原理时讲的加法器了。

看看51和85以二进制的形式相加：

  00110011
+ 01010101
----------
  10001000

注意看，由于二进制仅有0和1，那么出现进位的情况只能是1和1相加，并且进位其实相当于在其前一位加1，那么进位产生的1就可以表示为按位与的结果再往左移位一位，即

  00110011
& 01010101
----------
  00010001
<<
----------
  00100010

那么不考虑进位的相加结果是什么了，其实就是按位异或了，即

  00110011
^ 01010101
----------
  01100110

来看看“按位与，移位”和“按位异或”相加的结果：

  00100010
+ 01100110
----------
  10001000

怎么样？就是最终的答案了。所以只需要重复这个按位与和按位异或的过程，直到按位与的值为0（不产生进位），那么就得到最终结果了。来模拟一下

     00110011
     01010101
----------
& -> 00010001 << 1 -> 00100010
^ -> 01100110

     00100010
     01100110
----------
& -> 00100010 << 1 -> 01000100
^ -> 01000100

     01000100
     01000100
----------
& -> 01000100 << 1 -> 10001000
^ -> 00000000

     10001000
     00000000
----------
& -> 00000000
^ -> 10001000

output: 10001000

Python

class Solution:
    def getSum(self, a, b):
        """
        :type a: int
        :type b: int
        :rtype: int
        """
        mask = 0xffffffff
        sum = (a ^ b) & mask
        part = a & b
        while part:
            a = sum
            b = (part << 1) & mask
            sum = (a ^ b) & mask
            part = a & b
        if sum & 0x80000000:
            sum -= 0x100000000
        return sum

Java

public class Solution {
    public int getSum(int a, int b) {
        int sum = a ^ b;
        int part = a & b;
        while (part != 0) {
            int theA = sum;
            int theB = part << 1;
            sum = theA ^ theB;
            part = theA & theB;
        }
        return sum;
    }
}

C++

class Solution {
public:
    int getSum(int a, int b) {
        int sum = a ^ b;
        int part = a & b;
        while (part) {
            int theA = sum;
            int theB = part << 1;
            sum = theA ^ theB;
            part = theA & theB;
        }
        return sum;
    }
};