I don't think you are correct. Certainly not with a word size of 4. For very large word sizes, the early return will be a big win. But you are really under-rati

I don't think you are correct. Certainly not with a word size of 4. For very large word sizes, the early return will be a big win. But you are really under-rating how expensive the hashmap will be vs "bit munging". You could roll your own perfect hash, but you would end up with a solution that looks almost identical to TFA. If you use a stdlib hash, you are going to be chasing pointers all over memory to do a single insert / lookup. De-referencing a single pointer not in cache costs 50 - 100 clock cycles on a modern system. By the time you do one insert, TFA will have XOR'd at least 32 chars into its bit mask. And your cache won't be as nice as in TFA, slowing you down even more. Given the two scenarios: 1) bit munging, no early return 2) hash lookup, early return I would guess scenario 1 wins until word size gets above ~256. And obviously, we can add an early return to scenario 1 to make it unquestionably the fastest.