Question

面试题 65. 不用加减乘除做加法

题目描述

写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。

 

示例:

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

 

提示：

• a, b 均可能是负数或 0
• 结果不会溢出 32 位整数

解法

方法一：位运算

两数字 $a$, $b$ 求和。

假设 $a_i$ 和 $b_i$ 分别表示 $a$ 和 $b$ 的第 $i$ 个二进制位。一共有 $4$ 种情况：

$a_i$	$b_i$	不进位的和	进位
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

观察可以发现，“不进位的和”与“异或运算”有相同规律，而进位则与“与”运算规律相同，并且需要左移一位。

• 对两数进行按位 & 与运算，然后左移一位，得到进位；
• 对两数进行按位 ^ 异或运算，得到不进位的和；
• 问题转换为求：“不进位的数 + 进位” 之和；
• 循环，直至进位为 $0$，返回不进位的数即可（也可以用递归实现）。

时间复杂度 $O(\log M)$，空间复杂度 $O(1)$。其中 $M$ 为整数的最大值。

class Solution:
  def add(self, a: int, b: int) -> int:
    a, b = a & 0xFFFFFFFF, b & 0xFFFFFFFF
    while b:
      c = ((a & b) << 1) & 0xFFFFFFFF
      a, b = a ^ b, c
    return a if a < 0x80000000 else ~(a ^ 0xFFFFFFFF)

class Solution {
  public int add(int a, int b) {
    while (b != 0) {
      int c = (a & b) << 1;
      a ^= b;
      b = c;
    }
    return a;
  }
}

class Solution {
public:
  int add(int a, int b) {
    while (b) {
      unsigned int c = (unsigned int) (a & b) << 1;
      a = a ^ b;
      b = c;
    }
    return a;
  }
};

func add(a int, b int) int {
  if b == 0 {
    return a
  }
  return add(a^b, (a&b)<<1)
}

function add(a: number, b: number): number {
  while (b) {
    const c = (a & b) << 1;
    a ^= b;
    b = c;
  }
  return a;
}

/**
 * @param {number} a
 * @param {number} b
 * @return {number}
 */
var add = function (a, b) {
  if (b == 0) {
    return a;
  }
  return add(a ^ b, (a & b) << 1);
};

public class Solution {
  public int Add(int a, int b) {
    while (b != 0) {
      int c = (a & b) << 1;
      a = a ^ b;
      b = c;
    }

    return a;
  }
}

方法二

class Solution {
  public int add(int a, int b) {
    if (b == 0) {
      return a;
    }
    return add(a ^ b, (a & b) << 1);
  }
}