Search code examples
algorithmcomputation-theoryclrs

Why the 14 most significant bits of 17612864 is 67?

At the bottom of Page 264 of CLRS, the authors say after obtaining r0 = 17612864, the 14 most significant bits of r0 yield the hash value h(k) = 67. I do not understand why it gives 67 since 67 in binary is 1000011 which is 7 bits.

EDIT In the textbook: As an example, suppose we have k = 123456, p = 14, m = 2^14 = 16384, and w = 32. Adapting Knuth's suggestion, we choose A to be the fraction of the form s/2^32 that is closest to (\sqrt(5) - 1) / 2, so that A = 2654435769/2^32. Then k*s = 327706022297664 = (76300 * 2^32) + 17612864, and so r1 = 76300 and r0 = 17612864. The 14 most significant bits of r0 yield the value h(k)=67.

Solution

  • 17612864 = 0x010CC040 = 

    0000 0001 0000 1100 1100 0000 0100 0000

    Most significant 14 bits of that is

    0000 0001 0000 11

    Which is 0x43, which is 67

    Also:

    int32 input = 17612864;
int32 output = input >> (32-14); //67