如何在没有 + 的情况下添加数字

Question

我在面试中被问到这个问题。我没有回答，实际上我不明白它是如何工作的。

int add(int x, int y)
{
    while (y != 0)
    {
        int carry = x & y;  
        x = x ^ y; 
        y = carry << 1;
    }
    return x;
}

我不是在问为什么它会产生正确的答案...首先，为什么算法最终会停止？对我来说不是那么明显。

为了让它停止，carry 必须变成 0。有人不能简单解释一下吗？

Answer 1

line 1 : int carry = x & y;

line 2 : x = x ^ y;

line 3 : y = carry << 1;

如果 x = 1； y = 2;

每个数字的二进制数：

0 = 00

1 = 01

2 = 10

3 = 11

对于第 1 行代码，

&（按位与）如果两个操作数中都存在二进制 AND 运算符，则将其复制到结果

x 为 1 => 01

y 为 2 => 10

结果进位 => 00 (0)

对于第 2 行代码，

^（按位异或）如果二进制异或运算符在一个操作数而不是两个操作数中都设置了位，则复制该位。

x 为 1 => 01

y 为 2 => 10

结果 x => 11 (3)

对于第 3 行代码，变量进位需要左移一位，所以现在进位是 0 => 00 并且左移 1 位意味着进位现在是 0。结果 y 是 (0)。 while 循环停止，因为 y 现在是 0。

x 的最终结果是 3。

希望对您有所帮助。

Answer 2

举个例子：

x=13(1101)
y=9(1001)

Loop 1:
-----------------
y!=0 -> carry=(1101)&(1001)=1001(9)  [AND Op]
x=(1101)^(1001)=0100(4)   [XOR Op]
y=carry<<1 -> y=(carry)x2=10010(18)

Loop 2:
-----------------
y!=0 -> carry=(0100)&(10010)=00000(0)
x=(0100)^(10010)=10110(22)
y=carry<<1 -> y=0

loop terminated.

因此，x是22.So，x^y存储和部分，x&y存储进位部分，然后进位(x&y)移位与x^y匹配数字，最后将它们异或并存入 x。 x 是结果。

Answer 3

简而言之，它是关于使用 y（以及它变成的 "carries/x&y"）修改 x 直到它成为两个整数的总和。例如，

y=1 (....0001), x=anything (either .....0 or .....1)
if x ends with 0, x&y=0
    //x^y = x becomes ....001 (thereby adding 1)
    //since x&y=0 the loop stops
if x ends with 1, x&y=1
    //x^y = x
    //since y= x&y<<1, new y=(.....000010)
    if x ends with 01, x&y=0
        //x^y = x becomes ....010 (thereby adding 1)
        //since x&y=0 the loop stops
    if x ends with 11, x&y=1
        //x^y = .....01
        //since y= x&y<<1, new y=(......000100)
        if x ends with 011
            //stuff happens and x becomes ....100 (thereby adding 1)
            //loop stops
        if x ends with 111
            //...
            //if x ends with 111111, x becomes ....1000000 (thereby adding 1)
            //if x ends with 1111111, x becomes ....10000000 (thereby adding 1)
            //if x ends with 11111111, x becomes ....100000000 (thereby adding 1)
            //well you get the idea

相同的逻辑适用于 y 的所有值，并且与普通加法没有太大区别，只是现在有 2 个可能的数字（0 和 1）而不是通常的 10（0 到 9）。

如何在没有 + 的情况下添加数字

How to add numbers without +

java

integer-arithmetic