371. 两整数之和

问题

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

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

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

思路

题目规定不能用加减乘除，那在计算机中对数字的运算就剩位运算了。所以肯定是位运算，那位运算如何实现加法呢？
首先，我们考虑我们都熟悉的十进制的加法运算。

例如，9 + 14 = 23，我们先不管进位，结果是13，个位产生一个进位，前进一位就是1*10，13 + 10 = 23。
再比如 204 + 948 = 1152，先不管进位，结果是142，再看进位，百位和个位产生了进位101，都前进一位，142 + 101 * 10 = 142 + 1010 = 1152。

再来看二进制，11 + 1 = 100，先不管进位，结果是10，再看最低位产生的进位 1，进一位就是左移一位，10 + 1 << 1 = 10 + 10 = 100。所以，步骤就是，a + b先算出不管进位的结果 result，再算出进位值 carry，再相加 ，即让a = result, b = carry，重复上述步骤, 直到不产生进位 carry 为0为止。最终结果为 a。

接下来，就是怎么用位进制产生result 和 carry了。不管进位的话，二进制相加位变化的情况是：

  • 0 + 0 => 0
  • 0 + 1 => 1
  • 1 + 0 => 1
  • 1 + 1 => 0

这是什么运算？这不就是异或运算！！
再看进位情况：

  • 0 + 0 => 0
  • 1 + 0 => 0
  • 0 + 1 => 0
  • 1 + 1 => 1

这是什么运算？这不就是与运算！！

所以，result = a^b，carry = ( a & b ) << 1
伪码：

  1. result = 0
  2. carry = 0
  3. do {
  4.     result = a ^ b;
  5.   carry = a & b;
  6.   a = result;
  7.   b = carry;
  8. } while(carry != 0)

491 dfs
189

代码(Rust)

pub fn get_sum(mut a: i32, mut b: i32) -> i32 {
    let mut sum = 0;
    let mut carry = 0;
    loop {
        sum = a ^ b;
        carry = (a & b) << 1;
        a = sum;
        b = carry;

        if carry == 0 {
            break;
        }
    }

    a
}