Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
function to count trailing zeros

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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.