跳转至

面试题 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$ 为整数的最大值。

1
2
3
4
5
6
7
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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
    public int add(int a, int b) {
        while (b != 0) {
            int c = (a & b) << 1;
            a ^= b;
            b = c;
        }
        return a;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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;
    }
};

1
2
3
4
5
6
func add(a int, b int) int {
    if b == 0 {
        return a
    }
    return add(a^b, (a&b)<<1)
}

1
2
3
4
5
6
7
8
function add(a: number, b: number): number {
    while (b) {
        const c = (a & b) << 1;
        a ^= b;
        b = c;
    }
    return a;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
/**
 * @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);
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
    func add(_ a: Int, _ b: Int) -> Int {
        var a = a
        var b = b
        while b != 0 {
            let c = (a & b) << 1
            a ^= b
            b = c
        }
        return a
    }
}

方法二

1
2
3
4
5
6
7
8
class Solution {
    public int add(int a, int b) {
        if (b == 0) {
            return a;
        }
        return add(a ^ b, (a & b) << 1);
    }
}

评论