在不使用 + 的情况下添加两个数字背后的实现逻辑?

Implementation logic behind adding two numbers without using +?

我在网上找到了这段代码。但是,我无法理解以下代码背后的逻辑:

public static int add(int a, int b) {
    if (b == 0) return a;
    int sum = a ^ b; // add without carrying
    System.out.println("sum is : "+sum);
    int carry = (a & b) << 1; // carry, but don’t add
    return add(sum, carry); // recurse
}

我们正在添加将整数转换为位并使用按位运算符。

EXOR 即 ^ : 0 ^0 和 1 ^1 =0 ,其他情况给出 1.

AND 即 & 1^1 =1 , ..其他情况给出 0.

<< 或左移。即左移并附加一个 0 位:0010 变为 0100

例如。

add(2,3)

2= 0010
3=0011

exor both : to get initial sum :  0001

carry : a &b = 0010  

Left shift by 1 bit : 0100 i.e 4

add(1,4)

exor both : 0001 0100 and u get 0101 i.e 5

carry = 0000 <<1 i.e 0000 .. 

因为进位是 0 ,它停止加法和 returns 前一个总和

让我们看一个例子(为简单起见,使用 8 位)

  a = 10010110
  b = 00111101

a^b 是异或运算,对于一个数字中有 1 而另一个数字中有 0 的地方,它给出 1。在我们的示例中:

a^b = 10101011

0 + 0 = 00 + 1 = 11 + 0 = 1 以来,唯一需要处理的列是两个数字中都有 1 的列。在我们的示例中,a^b

的答案更短
      00010100
    + 00010100

是。在二进制中,1 + 1 = 10,所以上面和的答案是

      00101000

(a & b) << 1。因此 a^b(a & b) << 1 的总和与 a + b.

相同

因此,假设进程一定会终止,那么答案就是正确的。但是该过程将终止,因为每次我们递归调用 sum 时,由于移位 <<,第二个参数最后至少还有一个 0。因此,我们保证最终会得到完全由 0 组成的第二个参数,这样 if (b == 0) return a; 行就可以结束这个过程并给我们一个答案。

这是table加法:

+   0  1
   -- --
0 | 0  1
1 | 1 10
      ▲

如果你忽略进位 你会发现它与 XOR 相同 table:

^   0  1
   -- --
0 | 0  1
1 | 1  0

因此,如果您将两个数字与按位异或相结合,您将得到无进位的逐位加法。

现在,什么是进位?只有当两个输入都为 1 时才会出现这种情况。

你可以用 AND 得到它:

&   0  1
   -- --
0 | 0  0
1 | 0  1

但是需要向左移动一位后加到和中,因为已经"carried"结束,所以(a & b) << 1

所以你可以计算不带进位的加法和进位本身。你如何在不使用加法的情况下将它们加在一起?简单的!通过递归这个加法的定义!

请参阅@pbabcdefp 关于为什么递归总是终止的回答。

举个例子,5+7:

5     = 101 (Base 2)
7     = 111 (Base 2)

现在考虑将两个(基数为 2)数字相加:

0+0 =  0 = 0 carry 0
1+0 =  1 = 1 carry 0
0+1 =  1 = 1 carry 0
1+1 = 10 = 0 carry 1

A+B的和(不带进位)为A^B,进位为A&B;当你携带一个数字时,它会向左移动一位(因此 (A&B)<<1)。

所以:

5    =  101 (Base 2)
7    =  111 (Base 2)
5^7  =  010 (sum without carrying)
5&7  = 101  (the carry shifted left)

然后我们可以递归添加进位:

A    =   010
B    =  1010
A^B  =  1000 (sum without carrying)
A&B  = 0010  (the carry shifted left)

然后我们可以再次递归,因为我们还有更多要携带:

A'    =  1000
B'    =   100 (without the leading zeros)
A'^B' =  1100 (sum without carrying)
A'&B' = 0000  (the carry shifted left)

现在没有东西可以带了-所以我们可以停下来,答案是1100 (base 2) = 12 (base 10)

该算法只是将十进制加法实现为(普通)二进制加法,使用 ors 进行加法运算,并使用移位的 ands 来查找进位,并将递归直到没有更多内容进位(这总是会发生,因为位移位每次都会向进位附加另一个零,因此每次递归至少多一位不会每次都生成进位值)。