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.


  • no go

    Two friends of mine were pretty enthusiastic about the Go language, so I tried writing a program in it yesterday. It is frustrating because despite…

  • playing with vala

    I actually was toying with making something like Vala back in college. It's pretty cute. Much like using the sane subset of C++, as you write code…

  • chromium.el

    This weekend I wrote some Emacs Lisp to write some utility functions I find useful for hacking on Chromium. It's fun to have a reason to use Lisp!…

  • 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.