Question

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.

Was it helpful?

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

OTHER TIPS

In a 32 bit world

17612864 = 00000001 00001100 11000000 01000000 (binary)

top fourteen bits = 00000001 000011 = 67

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top