18 different 32-bit generators each with period 2^32-1, consisting of all nonzero words (each generator is a single line of code consisting of 2 shifts, 2 XORs, and an AND, in C language ^ denotes XOR, & denotes AND, ~ denotes bit-complement): x ^= (x>>7)&(~(1<<3)); x ^= (x<<1); x ^= (x>>5)&(~(1<<4)); x ^= (x<<2); x ^= (x>>6)&(~(1<<6)); x ^= (x<<1); x ^= (x>>6)&(~(1<<7)); x ^= (x<<1); x ^= (x>>13)&(~(1<<7)); x ^= (x<<4); x ^= (x>>5)&(~(1<<8)); x ^= (x<<6); x ^= (x>>13)&(~(1<<8)); x ^= (x<<6); x ^= (x>>5)&(~(1<<9)); x ^= (x<<2); x ^= (x>>8)&(~(1<<10)); x ^= (x<<9); x ^= (x>>13)&(~(1<<10)); x ^= (x<<6); x ^= (x>>8)&(~(1<<11)); x ^= (x<<9); x ^= (x>>13)&(~(1<<11)); x ^= (x<<4); x ^= (x>>8)&(~(1<<12)); x ^= (x<<9); x ^= (x>>8)&(~(1<<13)); x ^= (x<<9); x ^= (x>>5)&(~(1<<17)); x ^= (x<<2); x ^= (x>>5)&(~(1<<18)); x ^= (x<<6); x ^= (x>>6)&(~(1<<18)); x ^= (x<<1); x ^= (x>>6)&(~(1<<19)); x ^= (x<<1); There are also various re-coded versions of these obtained by time-reversal and/or bit-order-reversal, etc. The AND-mask here was always taken to have all bits 1 except for a single hole. But entirely general masks also would be possible in an enormous number of possible ways, roughly 0.2% of parameter choices in x ^= (x>>A)&C; x ^= (x<<B) work to yield period = 2^32-1. For 64-bit words, it turns out we can save an instruction since the all-1's AND-mask happens to yield a solution: x ^= (x<<7); x ^= (x>>9); has period=2^64-1. This has exactly 3 more variants arising from time- and/or bit-order-reversal but aside from that is unique. For 16-bit words, these work: x ^= (x>>2)&(~(1<<2)); x ^= (x<<1); x ^= (x>>7)&(~(1<<3)); x ^= (x<<2); x ^= (x>>7)&(~(1<<5)); x ^= (x<<2); x ^= (x>>2)&(~(1<<11)); x ^= (x<<1); How to find these: All the above generators are linear transformations of vectors over the 2-element field GF(2) and the period is the order of the linear transformation. By fast matrix powering over GF(2) you verify (for a good parameter choice) that no divisor of 2^wordsize-1 is the period, but 2^wordsize-1 is. Bad parameter choices that do not pass that test are discarded. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)