How are the prime numbers encoded in Knuth's example of fitting primes into memory cache? Could somebody please help me understand what is going on here (in plain English)? I think that $(k \mathbin{\&amp;} 63)$ has the effect of modular division. Is that right? How are the primes encoded / how can I know exactly where a number starts and ends by moving my finger across each 64-bit word? 

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, ...




  [The goal is to make] a table of all odd prime numbers less than 1024, so that we can easily decide the primality of a small integer.



The ultimate package density is achieved when we have 1-bit items.
We can cram them into a 64-bit word.
Only 64-bit numbers are required.
To test whether $2k+1$ is prime, for $0 ≤ k &lt; 512$, simply compute the following in a 64-bit register, and see if the leftmost bit is 1:


$$P_{\lfloor k/64\rfloor} &lt;&lt; (k \mathbin{\&amp;} 63)$$

P is in big-endian format. Q is in little-endian format.


P0 —0111011011010011001011010010011001011001010010001011011010000001, 
P1 —0100110000110010010100100110000110110000010000010110100110000100, 
P2 -1001001100101100001000000101101000000100100001101001000100100101, 
P3 -0010001010001000011000011001010010001011010000010001010001010010, 
P4 —0000110000000010010000100100110010000100100110010010110000010000, 
P5 -1101001001100000101001000100001000100001000100100101000100101000, 
P6 —1010000001000010000011000011011000010000001011010000001011010000, 
P7 -0000010100010000100010100100100000010100100100010010000010100110.



For little-endian, $$Q_{\lfloor k/64\rfloor} &gt;&gt; (k \mathbin{\&amp;} 63) $$

and look at the rightmost bit of the result.


Q0 — 1000000101101101000100101001101001100100101101001100101101101110, 
Q1 - 0010000110010110100000100000110110000110010010100100110000110010, 
Q2 - 1010010010001001011000010010000001011010000001000011010011001001, 
Q3 - 0100101000101000100000101101000100101001100001100001000101000100, 
Q4 — 0000100000110100100110010010000100110010010000100100000000110000, 
Q5 — 0001010010001010010010001000010001000010001001010000011001001011, 
Q6 — 0000101101000000101101000000100001101100001100000100001000000101, 
Q7 — 0110010100000100100010010010100000010010010100010000100010100000;



– The Art of Computer Programming. Volume 4, Fascicle 1. Bitwise Tricks and Techniques. Binary Decision Diagrams. p.5
P is in big-endian format.
  P0 —0111011011010011001011010010011001011001010010001011011010000001, 


The first bit, 0, means 2*0 + 1 = 1 is not a prime.
The second bit, 1, means 2*1 + 1 = 3 is a prime.
The third bit, 1, means 2*2 + 1 = 5 is a prime.
The fourth bit, 1, means 2*3 + 1 = 7 is a prime.
The fifth bit, 0, means 2*4 + 1 = 9 is not a prime.
The sixth bit, 1, means 2*5 + 1 = 11 is a prime.
The seventh bit, 1, means 2*6 + 1 = 13 is a prime.
The eighth bit, 0, means 2*7 + 1 = 15 is not a prime.
The ninth bit, 1, means 2*8 + 1 = 17 is a prime.
And so on.


  P1 —0100110000110010010100100110000110110000010000010110100110000100,


The first bit, 0, means 2*64 + 1 = 129 is not a prime.
The second bit, 1, means 2*65 + 1 = 131 is a prime.
The third bit, 0, means 2*66 + 1 = 133 is not a prime.
The fourth bit, 0, means 2*67 + 1 = 135 is not a prime.
The fifth bit, 1, means 2*68 + 1 = 137 is a prime.
The sixth bit, 1, means 2*69 + 1 = 139 is a prime.
The seventh bit, 0, means 2*70 + 1 = 141 is not a prime.
The eighth bit, 0, means 2*71 + 1 = 143 is not a prime.
The ninth bit, 0, means 2*72 + 1 = 145 is not a prime.
And so on.


  P2 -1001001100101100001000000101101000000100100001101001000100100101, 


The first bit, 1, means 2*128 + 1 = 257 is a prime.
And so on.


  P3 -0010001010001000011000011001010010001011010000010001010001010010,


The first bit, 0, means 2*192 + 1 = 385 is not a prime.
And so on.

And so on.


  P7 -0000010100010000100010100100100000010100100100010010000010100110.


The first bit, 0, means 2*448 + 1 = 897 is not a prime.
And so on.
The last bit, 0, means 2*511+1 = 1023 is not a prime.  


  Could somebody please help me understand what is going on here (in plain English)? I think that (k&amp;63) has the effect of modular division. Is that right? How are the primes encoded / how can I know exactly where a number starts and ends by moving my finger across each 64-bit word?


If you have read the above explanation for many bits in P0, P1, ..., P7, the answer to your questions should be obvious now. For a number $2k+1$, $\lfloor k/64\rfloor$, the quotient of $k$ divided by 64, is which $P$ should be used. $k \mathbin{\&amp;} 63$, the remainder of $k$ divided by 64 is how many bits you should move to the right to find its primeness-indicator bit.