Most significant bit algorithm
Author Message
Most significant bit algorithm

Quote:

> I need to write an algorithm in C, to:
> 1) determine the most significant set bit
> in a byte/int/long whatever. I am looking for an efficient algorithm
> that does not invlove iterating through every bit position individually.

There is no Standard C function for this (traditionally called
"find first one bit").  Followup has been set accordingly.
To get that thread started off, here is a scheme that you
might consider:

For example assume a 64-bit word:
If the whole word is 0, return a failure-to-find indication.
Set bit location accumulator to 0 and total mask to 0xFFFFFFFFFFFFFFFF.
Mask word with 0xFFFFFFFF00000000 to see if first one bit is in the
left half of the word; if so, add 32 to the bit location accumulator
by ANDing with the complement (~) of this mask.
(This first mask update step can be simplified by omitting the inits
and just storing 32 or 0 and the appropriate mask.)
Mask with total mask and 0xFFFF0000FFFF0000 to see if " is in left
half of whatever half was just determined; if so add 16 to accumulator
by ANDing with the complement (~) of this mask.
....
Mask with " 0xAAAAAAAAAAAAAAAA to see if " is in odd # bit position;
The above can be done in a compact loop, but since you're worried
about efficiency the loop should be completely unrolled and the
Accumulator now contains bit location (counting from right starting
with 0).  If you performed the final mask update, the total mask is
now the isolated first one bit.

Of course, the last one bit can be found in a similar fashion.

Now that the general idea is exposed, try to find optimizations.
and new mask each time, update the original word by masking it with
the new contribution to the total mask and don't maintain a total