XOR operator - How does it work?

Question

Could you explain to me in plain English what the XOR ( ^ ) operator is and what it does in the following code:

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

Answer 1

XOR means exclusive or. This ensures that either A or B are true, but both are both. In this case, we perform a bitwise operation so that you can make a small graph of the results, they are as follows:

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

Since you apply it to integers, the above results apply to every bit in the operands. So let's just say that you have values ​​1, 2, 3 for height, length and width respectively.

First you will have

0001 ^ 0010, which leads to 0011, then it will be XOR'd at 3, so 0011 ^ 0011, which gives you 0000

EDIT: providing a wiki link from comments in addition to my explanation; http://en.wikipedia.org/wiki/Exclusive_or#Computer_science

EDIT: Why 0001 ^ 0010 lead to 0011 ?

So it’s best to do it in half. Consider an operator iterating over two sets of bits and comparing their pairs. Thus, in this case, it allows you to work from right to left (least significant for most in this case).

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

so with you you get 0011 . Basically, take each pair of input and specify a truth table for the result. The comment shows output with an x value that has not yet been calculated.

As for collisions, yes, in this case there are many collisions. If I said that it would be unique, it would be a bad choice. I really mean that if you have 2, 8, 4, since your XOR'n values ​​in this order will always give the same value.

Answer 2

When you develop a little, you see a lot of XOR between the fields in the getHashCode() methods, because this is a safe way to get the signature of objects. The concept of a signature is that it is like an imprint of an object, and it should fit in 32 bits. This signature is used by a number of objects as a quick comparison (although if you plan to use it for this, take a look at this Wikipedia article because you need to be careful about equality and hash codes) or for some kind of address (as in the case with .net Dictionary and Java HashMap ).

The obvious solution for me to get the Box fingerprint is to simply add the values, so if any of them changes, you get another fingerprint: bx.Height + bx.Length + bx.Width

Given that the equality operation can be really expensive (i.e. very slow) if we need to check the equality of two blocks:

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

Instead of doing a full comparison in the same way, we can compare the two hash codes, see that they are different, and skip the full equality comparison. In the dictionary, it is very important to give us a quick method of finding a bin (element) to place an object.

But if any of these values ​​is too large, we can get an integer overflow exception, so instead of using addition, we use XOR. Another solution that is unique enough to C # is to use an unchecked{ ... } block, but using XOR is considered more elegant.

There is one more subtle thing that we can do to improve performance, and you will see it with the help of multi-user hashcode methods (for example, those released by ReSharper or IntelliJ): we can make a question of order by shifting (multiplying) each value.

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

Now what happens is that every field of your hash code effectively takes place in the resulting 32 bits. This means that there are two blocks:

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

will not have the same hash codes (they will have the same hash codes with your current system, but they are different!)

There is more than you wanted to know about hash codes, but I will say one more thing.

In both Java / Scala and the .net framework, if you overload either equals or hash-code, you must also overload the other. You must also make sure that if two objects A and B have different hash codes, then calling A.Equals (B) must be false.