不用加号的加法-编程-IT技术博客

不用加号的加法

时间:2021-04-20 23:50:00 浏览: 字体: 放大 缩小


题目描述

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

Note:

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

解题思路

不用加法运算符实现加法,我们来看计算机底层是如何实现加法的。

1+1=101+0=10+1=10+0=0在这四种情况中,若不考虑进位,则
1+1=01+0=10+1=10+0=0。我们可以看到在不考虑进位的情况下,两二进制位相加的结果就是异或的结果。
而如果考虑进位,那么只有1+1的情况下有进位,即&运算为1,代表进位。

考虑数A、B,其二进制表示:\(A_2\)\(B_2\)。则有:

\[A_2+B_2=(A_2 {\wedge} B_2)+(A_2{\&}B_2)<<1 \]

\(A_2 {\wedge} B_2\)表示不带进位的数,\((A_2{\&}B_2)<<1\)表示进位数。
两者相加即为结果。
例如,要计算:1101+1001
不考虑进位:1101^1001=0100
考虑进位:1101&1001=1001,而1001<<1=10010
两者求和:0100+10010=10110即为结果。

但是上面对进位和不进位的两部分求和还是用到了加法,不能用加法怎么办?递归地将两部分视为新的\(A_2\)\(B_2\),直到进位为0。

考虑负数和0?由于计算机底层采用补码,符号位参与运算,因此,上述方法对于计算正负数还是0的加法没有区别。

代码

递归版

class Solution {
    public int add(int a, int b) {
        if((a & b) == 0){
            return a ^ b;//没有进位,直接返回
        }
        return add(a ^ b,(a & b) << 1);
    }
}

非递归版

class Solution {
    public int add(int a, int b) {
        while(b!=0){
            int tmp = a ^ b;//不考虑进位
            b = (a & b) << 1;//单独考虑进位
            a = tmp;//由于不能相加,递归地计算进位和不进位的值
        }//直到进位为0
        return a;
    }
}

标签: 不用加号的加法不用加号加法