Judy trick

Via brad via avva, from the source of Judy:

// Test if Word has any of the 4 bytes == ‘\0’:
//
// This arcane code takes advantage of the CPU having a fast barrel shifter and
// a carry bit. Doug stole this code from elsewhere, and we know it works, but
// we really can’t explain why.

#define NOZEROBYTE(Word) \
((((((Word) - 0x01010101) | (Word)) ^ (Word)) & 0x80808080) ? 0 : 1)

It took me a while to follow, but it’s not that bad after I understood it. Consider it a series of steps:

1. Subtracting 0x01010101 subtracts 1 from each byte, which forces a carry into any byte that is 0 already.
2. (A | B) ^ B, as you can prove to yourself, zeros all bits in A that are set in B.
3. A & 0x80808080 tests the high bit in each byte.