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
.
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