How are the prime numbers encoded in Knuth's example of fitting primes into memory cache?
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.