为什么使用XOR而不是OR？

Question

为什么使用XOR而不是OR？

4

  uint64_t k1 = 0;
  uint64_t k2 = 0;

  switch(len & 15)
  {
  case 15: k2 ^= ((uint64_t)tail[14]) << 48;
  case 14: k2 ^= ((uint64_t)tail[13]) << 40;
  case 13: k2 ^= ((uint64_t)tail[12]) << 32;
  case 12: k2 ^= ((uint64_t)tail[11]) << 24;
  case 11: k2 ^= ((uint64_t)tail[10]) << 16;
  case 10: k2 ^= ((uint64_t)tail[ 9]) << 8;
  case  9: k2 ^= ((uint64_t)tail[ 8]) << 0;

(tail的类型是uint8_t *)

就我所看到的，它与OR操作没有什么不同。在这里使用XOR有什么区别呢？这是一种优化吗？如果是的话，是哪种优化？还是说我对这两个运算符的差异存在误解？

我已经知道XOR和OR之间的差异。但在这种情况下，由于在开始时将值清零并且XOR的值不重叠，因此行为根本不应该与OR有任何不同。所以我想知道为什么作者选择了XOR（在我看来，OR传达了它的意图要比XOR好）。

- Sedat Kapanoglu

1

你漏掉了从一个 case 到下一个 case 的 fallthrough。这看起来像是 Duff's Device 的一种形式。 - John Bollinger

3

CPU的速度是由时钟控制的，因此门电路的速度对性能无关紧要。 - Havenard

4

也许它最初是被设计为有重叠之处，然后作者以某种方式进行了更改。无论如何，“异或”感觉更具“密码学”意义。 - ZisIsNotZis

2

如果你说作者应该使用OR，那我们也可以说作者应该直接使用ADD。 - smac89

1

@smac89 ADD 意味着算术运算，而不是位运算。这里的意图显然是位运算（在正确的位位置上叠加字节以获得整数）。OR 是此处所做操作的最佳选择。 - Sedat Kapanoglu

显示剩余20条评论

2个回答

-1

为什么要使用异或运算符而不是或运算符？

当代码可以使用“|”或“^”来获得和存档相同的功能时，首选的应该反映更大的问题。

“^”保留熵@Nominal Animal。

当代码试图形成哈希（如MurmurHash3中的哈希）时，“^”比“|”更好。 "^"翻转位，通常导致1和0的公平分布。 "|"偏向于制造1。

许多哈希算法将“a”和“b”“添加”在一起，就像没有进位的二进制加法一样，也就是说，“a ^ b”而不是“a | b”。因此，在这个哈希算法的上下文中，“^”传达了更好的算法意图。

有时候我会遇到使用|的哈希代码，不幸的是结果会出现偏差，而使用^则没有问题。在我看来，在哈希代码中使用|是一个提示，说明可能存在偏差。

- chux - Reinstate Monica

1

在哈希算法中，“或”和“异或”的核心区别在于，“异或”操作保留了参数的熵（“随机性”），而“或”则不保留。“异或”不同均匀随机源的结果仍然是均匀随机的，但“或”不是，因为二进制结果将具有比零更多的一（如chux所描述的那样，“偏向”）。 - Nominal Animal

在这种情况下，使用OR不会导致熵的损失，因为位的放置不重叠。该代码部分与密码学无关，它只是将可变数量的字节转换为整数的代码。 - Sedat Kapanoglu

@chux 我理解你的观点，但我的问题特别针对OR和XOR何时可以互换，就像这个例子一样。你提到的熵案例意味着它们不能互换。 - Sedat Kapanoglu

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- klutt · Accepted Answer

是的，在这种情况下，它们是完全等价的。此外，由于它们是等价的，编译器可以自行使用此功能进行优化。当您编译时，无法保证它实际上是或xor xor。实际上，在更一般的层面上，只要编译器生成的代码的可观察行为相同，您就不能保证它将是其中任何一个。

使用异或的一个合理原因是它是程序员所想到的第一件事，或者代码最初是以重要性为基础编写的，但后来被改成了不重要的版本。但由于在这种情况下它们是等价的，很难知道。