面试题 17.01-不用加号的加法(Add Without Plus LCCI)

原文链接: https://leetcode-cn.com/problems/add-without-plus-lcci

英文原文

Write a function that adds two numbers. You should not use + or any arithmetic operators.

Example:

Input: a = 1, b = 1
Output: 2

Note:

a and b may be 0 or negative.
The result fits in 32-bit integer.

中文题目

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

示例:

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

提示：

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

通过代码

高赞题解

思路描述：不能使用 + 或者其他算术运算符，那么使用位运算即可。

对于任意两个数相加，我们都可以把他们转换成二进制之和，比如

8 + 5 = 1000

+ 101

= 1101

对于每个位相加我们可以使用，因为 0 + 1 = 1，1 + 1 =10，0 + 0 = 0，所以我们可以使用异或运算符，因为相同位如果同为 0 或 1相加对应位其实都变成 0，唯一的区别是有无进位而已。

所以我们要记录下每次相加会产生的进位，我们注意到其实只有相同位均为 1 的时候下一位相加才会产生进位，所以我们可以使用与运算符，然后左移一位用到下一位的计算上去。

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