Getting the Leftmost Bit

Question

I have a 5 bit integer that I'm working with. Is there a native function in Objective-C that will let me know which bit is the leftmost?

i.e. I have 01001, it would return 8 or the position.

Thanks

Answer 1

You can build a lookup table, with 32 elements: 0, 1, 2, 2, 3, etc.

Answer 2

This is effectively the same operation as counting he number of leading 0s. Some CPUs have an instruction for this, otherwise you can use tricks such as those found in Hacker's Delight.

It's also equivalent to rounding down to the nearest power of 2, and again you can find efficient methods for doing this in Hacker's Delight, e.g.

uint8_t flp2(uint8_t x)
{
    x = x | (x >> 1);
    x = x | (x >> 2);
    x = x | (x >> 4);
    return x - (x >> 1);
}

See also: http://stackoverflow.com/questions/2679815/previous-power-of-2

Answer 3

Stanford Bit Twiddling Hacks have lots of examples of how to accomplish this.

Answer 4

If you mean the value of whatever bit is in position five from the right (the "leftmost" of a five-bit value), then:

    int value = 17;
    int bit = (value >> 4) & 1; // bit is 1

If you mean the position of the leftmost bit that is 1:

    int value = 2;
    int position;
    for (position = 0; position < 5; position++) {
            int bit = (value >> position) & 1;
            if (bit == 1)
                    break;
    }
    // position is 1

Position will be 0 for the bit furthest to the right, 4 for the leftmost bit of your five-bit value, or 5 if all bits where zero.

Note: this is not the most effective solution, in clock cycles. It is hopefully a reasonably clear and educational one. :)

Answer 5

NSInteger value = 9;
NSInteger shift = 1;
for(NSInteger bit = value; bit > 1; bit = value >> ++shift);
NSInteger leftmostbit = 1 << shift;

Works for every number of bits.

Answer 6

I don't know objective C but this is how I would do it in C.

pow(2, int(log2(Number))

This should give you the left most 1 bit value.

PLEASE SEE STEPHEN CANON'S COMMENT BELOW BEFORE USING THIS SOLUTION.

Answer 7

To clear all bits below the most significant bit:

while ( x & (x-1) ) x &= x - 1;
// 01001 => 01000

To clear all bits above the least significant bit:

x &= -x;
// 01001 => 00001

To get the position of the only set bit in a byte:

position = ((0x56374210>>(((((x)&-(x))*0x17)>>3)&0x1C))&0x07);
// 01000 => 3

In libkern.h there is a clz function defined to count leading zeros in a 32 bit int. That is the closest thing to a native Objective-C function. To get the position of the most significant bit in an int:

position = 31 - clz( x );
// 01001 => 3

Answer 8

If you don't want to use a table lookup, I would use 31 - __builtin_clz(yourNumber).

__builtin_clz( ) is a compiler intrinsic supported by gcc, llvm-gcc, and clang (and possibly other compilers as well). It returns the number of leading zero bits in an integer argument. Subtracting that from 31 gives you the position of the highest-order set bit. It should generate reasonably fast code on any target architecture.

Answer 9

With VC++ have a look at _BitScanReverse/(64) in