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

and update total mask by ANDing with this mask, else update total mask

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

and update total mask by ANDing with this mask, else update total mask

by ANDing with the complement (~) of this mask.

Mask with total mask and 0xFF00FF00FF00FF00 to see if " " " add 8 " "

....

Mask with " 0xAAAAAAAAAAAAAAAA to see if " is in odd # bit position;

if so add 1 " (last mask update is not necessary).

The above can be done in a compact loop, but since you're worried

about efficiency the loop should be completely unrolled and the

parenthesized optimizations made.

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.

For example, instead of masking the original word with total mask

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

mask variable at all.

--