题解：AcWing 85.不用加减乘除做加法

题目链接

AcWing 85.不用加减乘除做加法

引用

简单看了一下大佬们的题解，真的是操了，一堆骚操作，完全不懂2333，有用low_bit+异或+与实现的，也有和y总一样的异或+与。对比了大佬的题解发现一些细节方面的问题，等会待我一一道来。全加器感兴趣的小伙伴也可以去了解一下，慕明大佬写的题解用到了low_bit算法也可以观摩一下，加深对位运算的理解，对以后做题有意想不到的帮助哦

慕明 AcWing 85. 不用加减乘除做加法 lowbit操作

咲张熊猫人 AcWing 85. 不用加减乘除做加法

Elpsy_3 AcWing 85. 不用加减乘除做加法 C++ 最简单易懂的思路

GRID AcWing 85. 不用加减乘除做加法 全加器，位运算，C++

cornerCao AcWing 85. 不用加减乘除做加法

贺谦 AcWing 85. 不用加减乘除做加法

题目描述

写一个函数，求两个整数之和，要求在函数体内不得使用 ＋、－、×、÷ 四则运算符号。

样例

输入：num1 = 1 , num2 = 2

输出：3

算法

(位运算) $O(1)$

异或 相同为0，不同为1，所以可以起到相加的作用

与 同为1为1，其余为0，起到了进位作用

因为不能使用加减乘除运算，所以我们只能用位运算来实现，因为计算机中的任何运算最终都是位运算来完成的。

那么应该怎么做呢？

加法一共分成两步，首先按位相加，其次再处理进位。
聪明的小伙伴应该发现了异或运算的结果其实相当于两个二进制数相加，但没有进位，那么如果进位的话怎么办呢，那些大佬已经帮我们解决了这一问题，进位的话只要将这两个数相与然后右移1位就行了，不断迭代，直到进位为0，因为与的结果迟早是0，而右移的结果也迟早是0。这样我们就解决了进位与不进位的处理方式。只要进位为0，那么我们的计算就停止

时间复杂度 $O(1)$

最多计算32次，所以时间复杂度是 $O(1)$ 的

C++ 代码

class Solution {
public:
    int add(int num1, int num2){
        while (num2) {
            //可以把num2想象为进位，每次迭代时异或这两个数就是让他们直接相加不进位，然后再处理进位，接着再相加
            int sum = num1 ^ num2;
            int carry = (num1 & num2) << 1;
            num1 = sum, num2 = carry;
        }
        return num1;
    }
};