Find the highest order bit in C

Question

Hi, 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

Answer 1

Continually remove the low order bit comes to mind...

int highest_order_bit( int x )
{
    int y = x;
    do { 
        x = y;
        y = x & (x-1); //remove low order bit
    }
    while( y != 0 );
    return x;
}

Answer 2

This should do the trick.

int hob (int num)
{
    if (!num)
     return 0;

    int ret = 1;

    while (num >>= 1)
     ret <<= 1;

    return ret;
}

hob(1234) returns 1024
hob(1024) returns 1024
hob(1023) returns 512

Answer 3

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.

Answer 4

I would assume that you are working on an x86 architecture however it is important to understand the endian of the platform you are running when handling bitwise operations. Take a look at this article for a better idea: http://en.wikipedia.org/wiki/Endianness

Answer 5

The linux kernel has a number of handy bitops like this, coded in the most efficient way for a number of architectures. You can find generic versions in include/asm-generic/bitops/fls.h (and friends), but see also include/asm-x86/bitops.h for a definition using inline assembly if speed of is the essence, and portability is not.

Answer 6

A fast way to do this is via a look-up table. For a 32-bit input, and an 8-bit look-up table, in only requires 4 iterations:

int highest_order_bit(int x)
{
    static const int msb_lut[256] =
        {
            0, 0, 1, 1, 2, 2, 2, 2, // 0000_0000 - 0000_0111
            3, 3, 3, 3, 3, 3, 3, 3, // 0000_1000 - 0000_1111
            4, 4, 4, 4, 4, 4, 4, 4, // 0001_0000 - 0001_0111
            4, 4, 4, 4, 4, 4, 4, 4, // 0001_1000 - 0001_1111
            5, 5, 5, 5, 5, 5, 5, 5, // 0010_0000 - 0010_0111
            5, 5, 5, 5, 5, 5, 5, 5, // 0010_1000 - 0010_1111
            5, 5, 5, 5, 5, 5, 5, 5, // 0011_0000 - 0011_0111
            5, 5, 5, 5, 5, 5, 5, 5, // 0011_1000 - 0011_1111

            6, 6, 6, 6, 6, 6, 6, 6, // 0100_0000 - 0100_0111
            6, 6, 6, 6, 6, 6, 6, 6, // 0100_1000 - 0100_1111
            6, 6, 6, 6, 6, 6, 6, 6, // 0101_0000 - 0101_0111
            6, 6, 6, 6, 6, 6, 6, 6, // 0101_1000 - 0101_1111
            6, 6, 6, 6, 6, 6, 6, 6, // 0110_0000 - 0110_0111
            6, 6, 6, 6, 6, 6, 6, 6, // 0110_1000 - 0110_1111
            6, 6, 6, 6, 6, 6, 6, 6, // 0111_0000 - 0111_0111
            6, 6, 6, 6, 6, 6, 6, 6, // 0111_1000 - 0111_1111

            7, 7, 7, 7, 7, 7, 7, 7, // 1000_0000 - 1000_0111
            7, 7, 7, 7, 7, 7, 7, 7, // 1000_1000 - 1000_1111
            7, 7, 7, 7, 7, 7, 7, 7, // 1001_0000 - 1001_0111
            7, 7, 7, 7, 7, 7, 7, 7, // 1001_1000 - 1001_1111
            7, 7, 7, 7, 7, 7, 7, 7, // 1010_0000 - 1010_0111
            7, 7, 7, 7, 7, 7, 7, 7, // 1010_1000 - 1010_1111
            7, 7, 7, 7, 7, 7, 7, 7, // 1011_0000 - 1011_0111
            7, 7, 7, 7, 7, 7, 7, 7, // 1011_1000 - 1011_1111

            7, 7, 7, 7, 7, 7, 7, 7, // 1100_0000 - 1100_0111
            7, 7, 7, 7, 7, 7, 7, 7, // 1100_1000 - 1100_1111
            7, 7, 7, 7, 7, 7, 7, 7, // 1101_0000 - 1101_0111
            7, 7, 7, 7, 7, 7, 7, 7, // 1101_1000 - 1101_1111
            7, 7, 7, 7, 7, 7, 7, 7, // 1110_0000 - 1110_0111
            7, 7, 7, 7, 7, 7, 7, 7, // 1110_1000 - 1110_1111
            7, 7, 7, 7, 7, 7, 7, 7, // 1111_0000 - 1111_0111
            7, 7, 7, 7, 7, 7, 7, 7, // 1111_1000 - 1111_1111
        };

    int byte;
    int byte_cnt;

    for (byte_cnt = 3; byte_cnt >= 0; byte_cnt--)
    {
        byte = (x >> (byte_cnt * 8)) & 0xff;
        if (byte != 0)
        {
            return msb_lut[byte] + (byte_cnt * 8);
        }
    }

    return -1;
}

Answer 7

like obfuscated code? Try this:

1 << ( int) log2( x)

Answer 8

This can easily be solved with existing library calls.

int highestBit(int v){
  return ffs(v) << 1;
}

The Linux man page gives more details on this function and its counterparts for other input types.