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

Sun, 02 Mar 2003 22:14:09 GMT

 Page 1 of 1 [ 1 post ]

Relevant Pages