不用加减乘除做加法

题目 不用加减乘除做加法

image-f241e225

思路分析

image-02898d3c

不让用加减乘除 那就考虑位运算 十进制加法转换成二进制再做加法 结果是一样的

之前有一个-x=~x+1 但也只是能做到将a+b变成a--b 还是要用减法

那么换一个角度思考 模拟一下计算

手写加法的时候 不外乎就是做两件事 算两位的和 再看上一位有没有进位 再加上去

\(a{i}\)+ \(b{i}\) + 进位

那不妨把拆开来

先算 \(a{i}\)+ \(b{i}\) 之后再考虑进位

对于二进制来说 \(a{i}\)+ \(b{i}\) 相当于\(a{i}\)^ \(b{i}\)

相同为0 不同为1

0+0=0^0=0

0+1=0^1=1

1+0=1^0=1

1+1=1^1=1

所以不考虑进位的加法直接就是 \(a{i}\)^ \(b{i}\)

那么进位怎么办

只有1 1的时候才会进位吧

进位进的是1

那么要1 1得1

显然是&

但是这个进位应该是进在下一位

所以于\(a{i}\)& \(b{i}\) << 1

ok 这样一来 $a{i} $ \(b{i}\) 进位 就都有了

image-97b32f30

代码实现

class Solution {

public:

    int add(int num1, int num2){

        while(num2)

        {

            int sum=num1^num2;

            int carry=(num1 & num2)<<1;

            num1=sum,num2=carry;

        }

        return num1;

    }

};

同类题型

视频讲解

⬅️ 位运算 🏠 00-刷题理模型 ➡️ 中等计算