65. 不用加减乘除做加法

2020, Dec 25 One min read

1. 描述

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

2. 例子

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

3. 提示

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

4. 题解

时间复杂度: O(1)

空间复杂度: O(1)

不得使用加减乘除类的计算必定是使用位运算，但是需要注意编译器可能不允许 C++ 负值左移，需要将其先转换为无符号整数。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution
{
public:
    int add(int a, int b)
    {
        int sum, carry;
        while(b != 0)
        {
            sum = (a ^ b);
            carry = (unsigned int)(a & b) << 1;

            a = sum;
            b = carry;
        }

        return a;
    }
};

comments powered by Disqus