0

I have an array of 20 words/bytes storing a 160 bit number. How can I find the first nonzero bit starting from msb . I need to find the position of the bit and then accordingly from the first '1' position I need to do some operations.

Sampi
  • 87
  • 2
  • 4
  • 14
  • 3
    [This](http://stackoverflow.com/questions/671815/what-is-the-fastest-most-efficient-way-to-find-the-highest-set-bit-msb-in-an-i?rq=1) might be helpful – rath Aug 03 '13 at 08:35
  • 1
    possible duplicate of [Find most significant bit (left-most) that is set in a bit array](http://stackoverflow.com/questions/2589096/find-most-significant-bit-left-most-that-is-set-in-a-bit-array) – SomeWittyUsername Aug 03 '13 at 09:03

2 Answers2

6

If you're using gcc, there are builtin functions doing exactly that (and many other things)

http://gcc.gnu.org/onlinedocs/gcc-4.5.4/gcc/Other-Builtins.html

The one you're looking for is probably __builtin_clz (for unsigned int), __builtin_clzl (for unsigned long) or __builtin_clzll for unsigned long long.

From the documentation:

Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined

So go over your ints (longs? longlongs?) from the most significant until you find the first that isn't zero. Then use the appropriate __builtin_clz to find how many leading zeros it has, and 32 (64) minus that number is the location of the highest 1 bit in your number!

Of course you can always implement __builtin_clz for yourself if you want to be compatible with other compilers (as you should!)

rabensky
  • 2,864
  • 13
  • 18
0

You can iterate for each byte until you find the first that is != 0. For each byte that is equals to zero, increment a counter by 8.

Then with that byte, do a shift right operation (>> 1) until that value is equal to zero. In each shift, increment the previous counter by 1.

Miguel Prz
  • 13,718
  • 29
  • 42