Fast most significant bit

most_significant_bit.c

inline unsigned long msb_intrin(unsigned long x)
{
    const int zs = __builtin_clzl(x);
    return 1ul << (sizeof(x) * CHAR_BIT - zs - 1);
}

inline unsigned long msb_fast(unsigned long x)
{
    int bit_size = sizeof(x) * CHAR_BIT;

    #pragma unroll
    for (int j = 0; (1 << j) < bit_size; ++j)
        x |= x >> (1 << j);
    return x - (x >> 1);
}

inline unsigned long msb_bitset(unsigned long x)
{
    unsigned long t;
    do {
        t = x;
        x &= x - 1ul;
    } while (x != 0ul);
    return t;
}

tests.txt

msb_intrin:   O(1)                0.001 ms
msb_fast:     O(log(log(num)))    305.606 ms
msb_avg:      O(# of set bits)    1202.82 ms