c - 此函数如何仅使用按位运算符对 3 个整数求和？

Question

int sum3(int x, int y, int z) {

  /* use XOR to combine x, y, and z, use word2 to store carry bit. */

  int word1 = 0;
  int word2 = 0;

  word1 = (x^y) ^ z;
  word2 = ( (x&y) | (x&z) | (y&z) ) << 1;

  return sum(word1,word2);
}

我不明白其背后的“原因”。我知道这与进位有关

编辑:这是总和:

static int sum(int x, int y) {
  return x+y;
}

所以我撒谎了，它最后确实用了+

Answer 1

xor 在逻辑上是“无进位加法”

假设您有一台 1 位计算机。

0+0 = 0
0+1 = 1
1+0 = 1

到目前为止还好吗？

然后

1+1 = 0

在这里，我们知道答案是 2d 或 10b，但在 1 位机器上，2s 位丢失并溢出。

真值表正是您通过异或运算得到的结果。

0^0 = 0
0^1 = 1
1^0 = 1
1^1 = 0

那么如何判断进位发生在何处？这些只有在位位置相等时才会发生，这是通过 AND 测试的。所以在上面只有 1+1 导致进位。进位意味着在左移位置添加 1 位，因此 A&B << 1 给出新的进位。

您可以将其从 1 位扩展到任意数量的位，然后查看基本逻辑。它稍微复杂一些，因为您可能必须在整个操作过程中改变进位，但我们现在将忽略它(就像您的示例一样)。

现在我们可以考虑添加第三个数字。检查逻辑，您可以看到基本原理在这里也仍然有效。

1+1+1 = 3d = 11b = 1b if we throw out the overflow
1^1^1 = 1b  

溢出只能在每个位位置发生一次，因此检查所有组合以查看是否发生溢出(通过 AND)，然后将它们组合在一起得到所有进位。

虽然您拥有的逻辑不会扩展到 4 个值，因为它无法处理单个位置的多个进位(因为它将它们组合在一起，所以它只能表示任何位置的 1 个进位)。

您的算法并没有真正处理纹波，最后通过调用普通加法器(只是“+”操作)来解决这个问题。一个功能齐全的示例必须有不同的行为，也许是一次对 1 位进行操作。