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

Question

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

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
}

Answer 1

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

  a = 10010110
  b = 00111101

a^b是 xor，它给出 1对于有 1 的地方在一个数字和0在另一个。在我们的示例中:

a^b = 10101011

自 0 + 0 = 0 , 0 + 1 = 1和 1 + 0 = 1 ，唯一需要处理的列是具有 1 的列在这两个数字中。在我们的示例中，a^b无论对

的回答是什么

      00010100
    + 00010100

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

      00101000

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

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