function to count trailing zeros

gistfile1.md

Given an unsigned integer, return the number of trailing zero bits

Test framework:

#include <stdio.h>
#include <assert.h>

unsigned trailing_zeros(unsigned n) {
    // fill in this function
}

void do_it(unsigned input, unsigned expected) {
    unsigned output = trailing_zeros(input);
    assert(output == expected);
}

int main() {
    int i;
    for (i = 0; i < 10000000; i++) {
        do_it(0b10101100, 2);
        do_it(0b00000000, -1);
        do_it(0b00000000100010000, 4);
        do_it(0b00000000100000000, 8);
        do_it(0b01000100100100001, 0);
        do_it(0b0100010010010000100000, 5);
        do_it(0b1000000000000000000000, 21);
        // uncomment to add 64-bit test
        //do_it(0x1000000000, 36);
    }
}

The way I implemented it on the test:

Code

unsigned trailing_zeros(unsigned n) {
    if (n == 0) {
        return -1;
    }
    unsigned count = 0;
    while (n % 2 == 0) {
        count++;
        n >>= 1;
    }
    return count;
}

Output

$ gcc -o test test.c && time ./test

real	0m2.157s
user	0m2.160s
sys	0m0.000s
$ gcc -o test test.c && time ./test

real	0m2.171s
user	0m2.170s
sys	0m0.000s
$ gcc -o test test.c && time ./test

real	0m2.158s
user	0m2.150s
sys	0m0.010s

Bit Twiddling: Count the consecutive zero bits (trailing) on the right linearly 1

Code

unsigned trailing_zeros(unsigned n) {
    unsigned c;
    if (n) {
        n = (n ^ (n - 1)) >> 1;
        for (c = 0; n; c++)
            n >>= 1;
        return c;
    } else {
        return -1;
    }
}

Output

$ gcc -o test test.c && time ./test

real	0m2.303s
user	0m2.290s
sys	0m0.010s
$ gcc -o test test.c && time ./test

real	0m2.313s
user	0m2.320s
sys	0m0.010s
$ gcc -o test test.c && time ./test

real	0m2.292s
user	0m2.290s
sys	0m0.000s

BitTwiddling: Count the consecutive zero bits (trailing) on the right in parallel 2

Code

unsigned trailing_zeros(unsigned n) {
    if (! n) return -1;
    unsigned int c = 32; // c will be the number of zero bits on the right
    n &= -(signed) n;
    if (n) c--;
    if (n & 0x0000FFFF) c -= 16;
    if (n & 0x00FF00FF) c -= 8;
    if (n & 0x0F0F0F0F) c -= 4;
    if (n & 0x33333333) c -= 2;
    if (n & 0x55555555) c -= 1;
    return c;
}

Output

$ gcc -o test test.c && time ./test

real	0m1.066s
user	0m1.070s
sys	0m0.000s
$ gcc -o test test.c && time ./test

real	0m1.067s
user	0m1.070s
sys	0m0.000s
$ gcc -o test test.c && time ./test

real	0m1.065s
user	0m1.070s
sys	0m0.000s

Count the consecutive zero bits (trailing) on the right with modulus division and lookup 2

Code

static const unsigned Mod37BitPosition[] = // map a bit value mod 37 to its position
{
    -1, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13, 4,
    7, 17, 0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9, 5,
    20, 8, 19, 18
};

unsigned trailing_zeros(unsigned n) {
    return Mod37BitPosition[(-n & n) % 37];
}

Output

$ gcc -o test test.c && time ./test

real	0m0.972s
user	0m0.980s
sys	0m0.000s
$ gcc -o test test.c && time ./test

real	0m0.973s
user	0m0.970s
sys	0m0.000s
$ gcc -o test test.c && time ./test

real	0m0.974s
user	0m0.970s
sys	0m0.000s