8

While browsing the implementation of the generic Dictionary<TKey, TValue> class in mscorlib.dll, I noticed the following used many times to get a hash-key:

int num = this.comparer.GetHashCode(key) & int.MaxValue;

GetHashCode() returns an int. Am I mistaken in thinking that a bitwise AND between int.MaxValue and any integer x, will always return x?

Can someone explain why the & operator is used in the manner above?

MJ Richardson
  • 1,441
  • 12
  • 30

2 Answers2

11

The value of int.MaxValue is 0x7FFFFFFF — the most significant bit is zero. Hence when you perform a bitwise and with another int, you effectively zero-out the 'sign' bit. Note that because of the two's complement encoding used, -1 won't become 1 but rather 2,147,483,647.

Apparently, for some reason only positive integers are allowed in the num variable in you code sample.

Ondrej Tucny
  • 27,626
  • 6
  • 70
  • 90
  • 4
    The most likely reason for doing this is that the value of the result modulo number of buckets will be computed, to get the correct bucket. That wouldn't work right for negative numbers. – svick Jan 27 '12 at 01:40
  • I'd be willing to bet a whole dollar that the implementation of Dictionary in .NET does not care whether the hashcode is positive or negative, and that the person who wrote the code is doing it in a (probably ill-advised) attempt to try to avoid matching prime factorizations with the number of buckets: http://stackoverflow.com/questions/3613102/why-use-a-prime-number-in-hashcode – Chris Shain Jan 27 '12 at 01:47
  • @Chris: According to the OP, that code *is* from the .NET `Dictionary` implementation. As svick suggests, it's probably to ensure that the bucket number -- an array index, iirc -- is always positive. – LukeH Jan 27 '12 at 02:02
  • @LukeH you are absolutely right, misread the question entirely. – Chris Shain Jan 27 '12 at 02:04
2

It will not affect positive numbers

  • [0, int.MaxValue] --> remains unchanged
  • [int.MinValue, -1] --> will alter the sign bit
doblak
  • 3,036
  • 1
  • 27
  • 22
  • The second statement is incorrect. `int.MinValue & int.MaxValue == 0`. Negative values will returned as (value + 2147481498). – Hand-E-Food Jan 27 '12 at 01:38
  • `int.MinValue & int.MaxValue == 0` ... but that's exactly altering the sign bit, I guess that's correct. Anyway, Ondrej provided a better explanation. – doblak Jan 27 '12 at 01:45