Question

Find the highest order bit in C

what I'm after is something I can feed a number into and it will return the highest order bit. I'm sure there's a simple way. Below is an example output (left is the input)

1 -> 1
2 -> 2
3 -> 2
4 -> 4
5 -> 4
6 -> 4
7 -> 4
8 -> 8
9 -> 8
...
63 -> 32
 47  63191  47
1 Jan 1970

Solution

 93

From Hacker's Delight:

int hibit(unsigned int n) {
    n |= (n >>  1);
    n |= (n >>  2);
    n |= (n >>  4);
    n |= (n >>  8);
    n |= (n >> 16);
    return n - (n >> 1);
}

This version is for 32-bit ints, but the logic can be extended for 64-bits or higher.

2008-09-09

Solution

 42

fls bottoms out to a hardware instruction on many architectures. I suspect this is probably the simplest, fastest way of doing it.

1<<(fls(input)-1)
2012-12-29