2

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

JamesB41
  • 703
  • 10
  • 20

9 Answers9

7

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

ChrisW
  • 54,973
  • 13
  • 116
  • 224
  • A 32 element lookup table is far and away the best solution for this particular case. – Stephen Canon May 23 '10 at 21:38
  • 1
    @Stephen: only if you are 100% certain that the number of bits will **always** be 5 (or at least a relatively small number), and that you never want to do any optimisations, e.g. SIMD or GPGPU. – Paul R May 23 '10 at 21:40
  • @Paul R: Actually, a 32-byte lookup table is perfect for SIMD implementation on most vector architectures (On AltiVec or NEON it's a single instruction; SSE takes a little bit more work, but still isn't too bad). GPGPU may be another story, as you note. – Stephen Canon May 23 '10 at 22:40
  • @Stephen: true, this works well on AltiVec with vec_perm, but it gets ugly if you need to go beyond a 32 element LUT. It's much harder on SSE, unless you can assume SSSE3 (and hence PSHUFB). – Paul R May 24 '10 at 06:07
6

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: Previous power of 2

Community
  • 1
  • 1
Paul R
  • 208,748
  • 37
  • 389
  • 560
4
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.

Joost
  • 10,333
  • 4
  • 55
  • 61
  • 3
    Don't use `pow` for this. There's no language guarantee that `pow` will deliver an accurate power of two (it happens to on OS X, which is probably what's being targeted since the question is tagged `objective-c`, but it's not a portable assumption). It's also grossly inefficient on many platforms. You want `leftmostbit = 1 << shift`. – Stephen Canon May 23 '10 at 22:43
  • Thanks, you are right. I updated the code based on your comment. – Joost May 23 '10 at 22:55
2

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.

Stephen Canon
  • 103,815
  • 19
  • 183
  • 269
1

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

Paul R
  • 208,748
  • 37
  • 389
  • 560
neoneye
  • 50,398
  • 25
  • 166
  • 151
0

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. :)

Jakob Borg
  • 23,685
  • 6
  • 47
  • 47
0

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.

naivnomore
  • 1,291
  • 8
  • 14
  • 1
    This is incredibly slow on many platforms, and will give you the wrong answer on others (there's no guarantee that the `log2` or `pow` functions are correctly rounded -- even for small integers -- and on many platforms they are not). – Stephen Canon May 23 '10 at 22:46
  • @Stephen Canon - I just wanted to show one other method of solving this issue. You may be right on the slow issue but the whole idea of int casting is to get rid of the fraction part and once you do that pow() will always return you whole numbers. I am not aware that log2 and pow have rounding issues. If that is the case then the results can go wrong. – naivnomore May 24 '10 at 01:23
  • There is no guarantee that `pow(2, someInteger)` will always return a whole number. In fact, I have had the misfortune of using several platforms on which it did not (unfortunate, but true). – Stephen Canon May 24 '10 at 05:06
0

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
drawnonward
  • 53,459
  • 16
  • 107
  • 112
0

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

user411313
  • 3,930
  • 19
  • 16