Storing Lists in Registers

While working on my Wordle solver, I found a trick for treating integers as little lists. To keep memory usage down, I decided to pack the 5 letter words into a 32 bit integer. I use 6 bits per letter, leaving the top bit as a zero. This allows doing some SIMD tricks without having to expand the nibbles later.

However, sometimes it’s convenient to treat each Wordle word as a variable length list of characters, rather than the fixed size, 5 letter words that the game uses. Since the game uses up to 5 letters per word, and each letter consumes a 6 bit nibble, that leaves 32 - (5 * 6) = 2 bits left for use. 2 bits isn’t enough to encode a length field. However, we can use a trick similar to NULL terminated C strings: 1-bit prefixed ints.

This trick works by treating each 32 bit int as a [0, 5] length string of 6 bit values, prefixed by a 2 bit prefix. For example:

bits:  01EE EEEE DDDD DDCC CCCC BBBB BBAA AAAA
index: 1098 7654 3210 9876 5432 1098 7654 3210

The A-E bits represent the nibbles representing the letters, while the 01 prefix indicates the end of the string. To detect the length of the String, we count the number of leading 0 bits and divide by 6 to get the length:

MAX_CODES_PER_WORD = 5;
BITS_PER_CODE = 6;

int zeros = Integer.numberOfLeadingZeros(codeWord);

return MAX_CODES_PER_WORD - ((zeros - 1) / BITS_PER_CODE);

This is nice because Integer.numberOfLeadingZeros() is a single instruction on Intel architectures. Additionally, while dividing by 6 would normally be slow, the compiler optimizes this to a “magic number” division, i.e. a multiplication by (2^32) / 6. On my machine, calculating the length is around 3ns.