CODEWITHSUNDEEP
c
Sampi
Sampi

Reputation: 105

How to find the first non zero bit starting from msb

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.

Upvotes: 0

Views: 6910

Answers (2)

rabensky
rabensky

Reputation: 2934

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!)

Upvotes: 6

Miguel Prz
Miguel Prz

Reputation: 13792

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.

Upvotes: 0

Related Questions