跳转至

面试题 17.01. 不用加号的加法

题目描述

设计一个函数把两个数字相加。不得使用 + 或者其他算术运算符。

示例:

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

 

提示：

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

解法

方法一

思考

不用加减乘除做加法。循环里用加减会直接违背题意；把加数转成字符串再模拟竖式，实现偏长。

无进位和是异或，进位是与再左移一位。重复「无进位和 + 进位」直至进位为 \(0\)。

代码用 \(sum=a\oplus b\)、\(carry=(a\& b)\ll 1\)，再写回 \(a\)、\(b\)。符号位随算术移位自然处理，循环次数与位数同阶。

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
    func add(_ a: Int, _ b: Int) -> Int {
        var a = a
        var b = b
        var sum = 0
        var carry = 0

        while b != 0 {
            sum = a ^ b
            carry = (a & b) << 1
            a = sum
            b = carry
        }

        return a
    }
}

评论