XOR运算符-它是如何工作的

本文关键字：工作 何工作 运算符 XOR | 更新日期: 2023-09-27 18:27:46

你能用通俗的英语解释一下XOR（^）运算符是什么，以及它在以下代码中的作用吗：

public int GetHashCode(Box bx)
{
    int hCode = bx.Height ^ bx.Length ^ bx.Width;
    return hCode.GetHashCode();
}

XOR运算符-它是如何工作的

XOR代表异或。它确保A或B中的任何一个都是真的，但决不能两者都是。在这种情况下，我们正在进行逐位运算，这样你就可以制作一个很好的结果小图，它们如下所示；

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

由于您将其应用于整数，因此以上结果将应用于操作数中的每个位。假设你的高度、长度和宽度分别为1、2、3。

你会首先拥有

0001^0010得到0011，然后将其异或为3，所以0011^0011给你0000

编辑：提供评论中的wiki链接以补充我的解释；http://en.wikipedia.org/wiki/Exclusive_or#Computer_science

编辑：为什么0001 ^ 0010会导致0011？

所以最好一点一点地做。想象一下运算符在两组比特上迭代并比较它们的对。因此，在这种情况下，让我们从右到左进行工作（在这种情况中，从最不重要到最重要）。

1 ^ 0 = 1 // xxx1
0 ^ 1 = 1 // xx11
0 ^ 0 = 0 // x011
0 ^ 0 = 0 // 0011  - end of input

所以把它们拼凑在一起就得到了0011。基本上，取每对输入，并参考结果的真值表。注释显示输出，x是尚未计算的值。

关于碰撞，是的，在这种情况下有很多碰撞。如果我说它是独一无二的，那就太糟糕了。我真正的意思是，如果你有2、8、4作为你的值，那么按照这个顺序对它们进行异或运算总是会产生相同的值。

稍微细化一下，您会看到getHashCode()方法中的字段之间有很多XOR，因为这是获取对象签名的安全方法。签名的概念是，它就像一个物体的指纹，需要放入32位。这个签名被许多对象用作快速比较（不过，如果你打算使用它，可以看看维基百科的文章，因为你需要小心等式和哈希码），或者用于某种寻址（如.net的Dictionary和Java的HashMap）。

对我来说，获得Box指纹的明显解决方案是简单地将值相加，这样，如果其中任何一个值发生变化，你就会得到一个不同的指纹：bx.Height + bx.Length + bx.Width

考虑到相等运算可能非常昂贵（即非常慢），如果我们需要测试两个框的相等性：

  • Box {5, 10, 15}
  • Box {30, 40, 50}

我们可以比较这两个哈希代码，看看它们是否不同，然后跳过完全相等的比较，而不是进行完全相等的对比。在字典中，这对于为我们提供一种快速方法来找到一个bin（一个元素）来放入对象至关重要。

但是，如果这些值中的任何一个太高，我们可能会得到一个整数溢出异常，所以我们不使用加法，而是使用XOR。另一个解决方案是使用unchecked{ ... }块，也是C#独有的解决方案，但使用XOR被认为更优雅。

我们可以做一件更微妙的事情来提高性能，您可以通过许多自动生成的哈希代码方法（例如ReSharper或IntelliJ生成的方法）看到这一点：我们可以通过对每个值进行移位（相乘）来使顺序变得重要。

    public int hashCode() {
        int result = x;
        result = 31 * result ^ y;
        result = 31 * result ^ z;
        return result;
    }

现在发生的事情是，你的哈希代码中的每个字段实际上在产生的32位中都有一个位置。这意味着两个盒子：

  • Box {1, 20, 30}
  • Box {1, 30, 20}

不会有相同的哈希码（它们与您当前的系统具有相同的哈希代码，但它们不同！）

关于哈希码，有比你想知道的更多的东西，但我还要说一件事。

在Java/Scala和.net框架中，如果重载equals或hash代码，则必须同时重载另一个。还必须确保如果两个对象A和B具有不同的哈希代码，则对A.Equals（B）的调用必须为false。

相关文章：