getSum.md

371. 两整数之和

原题

不使用运算符 + 和 - ，计算两整数 a 、b 之和。

示例 1: 输入: a = 1, b = 2 输出: 3

示例 2: 输入: a = -2, b = 3 输出: 1

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/sum-of-two-integers

解法

public int getSum2(int a, int b) {
        while (b != 0) {
            int temp = a ^ b;
            
            int carry = (a & b) << 1;
            
            a = temp;
            b = carry;
        }
        return a;
    }

思路分析：

• 不能直接使用+号，显然只能通过位运算来完成加法操作。

• 在二进制的加法中

  •   1 + 0 = 1
      0 + 1 = 1
      0 + 0 = 0
      1 + 1 = 0 // 需要进位1
    

  • 忽略进位，这就是异或操作。（也可以这样来记，异或就是忽略进位的加法）

• 再考虑如何进位。假设现在使用 0101与0101相加

  •     0101
      + 0101
      = 1010
    

  • 如果两个数的某一位都是1，那么相加后要进位，向左进1。而两位中有一个0或者都是0，就不需要进位，所以进位的情况就是两个数相与后为1的位，像左进位。所以进位操作为(a & b) << 1

• 于是可以将加法拆分为两种个步骤

  • 两个数异或，得到忽略进位的加法结果。
  • 两个数相与后左移一位，得到进位信息。与忽略进位的加法结果进行相加。
  • 这时候，可能还会产生进位，所以要重复上述两个步骤，直到表示进位的数为0。

• 再举个例子。

  • 比如 5+3： 0101 ^ 0011 = 0110 十进制的6
  • 0101 & 0011 = 0001,但是这是进位数的右边一位，所以进行左移一位的操作得到 0010 十进制的2
  • 下一步继续计算 6 + 2 同样使用异或得到无进位数 0100（4），由与运算且左移1位 0100（4）
  • 再进行 4 + 4的计算：无进位数0000，进位数1000
  • 再进行 0 + 8的计算：无进位数1000，进位数0000 进位数为0，停止