bit-manipulation - 演练：使用位操作对 2 个整数求和

Question

我试图了解以下代码背后的逻辑，该代码使用位操作对 2 个整数求和：

def sum(a, b):
    while b != 0:
        carry = a & b
        a = a ^ b
        b = carry << 1

    return a

作为一个例子，我使用：a = 11和b = 7

二进制表示的 11 是二进制表示的1011 70111

然后我浏览了算法：

iter #1: a = 1011, b = 0111
  carry = 0011 (3 decimal)
  a = 1100 (12 decimal)
  b = 0110 (6 decimal)

iter #2: a = 1100, b = 0110
  carry = 0100 (4 decimal)
  a = 1010 (10 decimal)
  b = 1000 (8 decimal)

iter #3: a = 1010, b = 1000
  carry = 1000 (8 decimal)
  a = 00010 (2 decimal)
  b = 10000 (16 decimal)

iter #4: a = 00010, b = 10000
  carry = 00000 (0 decimal)
  a = 10010 (18 decimal)
  b = 00000 (0 decimal)

We Done (because b is now 0).

正如我们所看到的，在所有迭代a+b中始终是 18，这是正确的答案。但是我不明白这里实际发生了什么。的值a随着每次迭代而下降和下降，直到在最后一次迭代中突然弹出到 18。另外，在这个过程中，我们能从进位的价值中学到什么吗？

我很想了解这背后的直觉。

---

感谢@WJS 的回答，我想我明白了。

let's add 11 and 7 as before, but let's do it in the following order:
First, calculate it without the carry.
Second, calculate only the carry.
Then add both parts.

01011
00111
-----
01100 (neglecting carry)
00110 (finding only the carry)
-----
10010 (sum)

现在，要找到第一部分，我们怎样才能摆脱进位位？异或。为了找到第二部分，我们使用 AND 然后将其向左移动 1 位以将其放置在右侧位的“下方”。现在我们要做的就是将这两个部分相加。重点不是使用 + 运算符，那么我们该怎么做呢？递归！

我们将第一部分分配给，a第二部分分配给，b然后我们重复这个过程，直到b=0这意味着我们完成了。

标签： bit-manipulation

Answer 1

我认为如果您查看各个位会发生什么，这很容易理解。

第一步是计算进位，仅当两个位都为 1 时才会以二进制形式发生，因此 a&b 为每个位计算该进位。然后通过 XOR（忽略进位）进行按位加法，并且 XOR 起作用，因为：

0+0=0 (==0^0)
1+0=1 (==1^0)
1+1=0 (==1^1, generates carry bit which we ignore)

下一步是将进位左移（<<1），将其移至 b 并重复直到进位为空。