Irate Nate's weblog archives

» Friday, 19 December A.D. 2008

clz ctz trickery

This implementation of count leading/trailing zeroes (shown to me by one of my coworkers) definitely goes in the Nifty Hack category for today. I have to reproduce it here, just for my own archival abilities. Credit to Vadim Borshchev:

/*  Count leading zeros */

static const unsigned clz_magic = 0x7dcd629;
static const char clz_table[] = {
     0, 31,  9, 30,  3,  8, 18, 29,
     2,  5,  7, 14, 12, 17, 22, 28,
     1, 10,  4, 19,  6, 15, 13, 23,
    11, 20, 16, 24, 21, 25, 26, 27
};

unsigned clz (unsigned x) {
    x |= (x >> 1);
    x |= (x >> 2);
    x |= (x >> 4);
    x |= (x >> 8);
    x |= (x >> 16);
    return x ? clz_table[((clz_magic * x) + clz_magic) >> 27] : 32;
}

/* Count trailing zeros */

static const unsigned ctz_magic = 0xfb9ac52;
static const char ctz_table[] = {
    31,  0, 22,  1, 28, 23, 13,  2,
    29, 26, 24, 17, 19, 14,  9,  3,
    30, 21, 27, 12, 25, 16, 18,  8,
    20, 11, 15,  7, 10,  6,  5,  4
};

unsigned ctz (unsigned x) {
    return (x &= -x) ? ctz_table[(x * ctz_magic) >> 27] : 32;

}

posted by Nate @ 3:25PM