Evan Martin (evan) wrote in evan_tech,
Evan Martin

  • Music:

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.
So basically, you force there to be a carry into any zeroed bytes, then clear the high bits in any bytes that had the high bit set in the first place, and then finally you test if there are any high bits left over. If there are, there was a zeroed byte.


  • dremel

    They published a paper on Dremel, my favorite previously-unpublished tool from the Google toolchest. Greg Linden discusses it: "[...] it is capable…

  • your vcs sucks

    I've been hacking on some Haskell stuff lately that's all managed in darcs and it's reminded me of an observation I made over two years ago now (see…

  • google ime

    Japanophiles might be interested to learn that Google released a Japanese IME. IME is the sort of NLP problem that Google is nearly uniquely…

  • Post a new comment


    default userpic
    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.