Newsgroups

Newsgroups

Internet newsgroups are a great way of sharing information. There is an lcc newsgroup comp.compilers.lcc. Here is a question that appeared in another interesting newsgroup: comp.std.c that shows an interesting discussion:

From: [email protected]

I need to write an algorithm in C, to:

1) determine the most significant set bit

2) determine the least significant set bit

in a byte/int/long whatever. I am looking for an efficient algorithm that does not involve iterating through every bit position individually.

Cheers

Serin

Many people answered, and the discussion about which algorithm to use was a very informative one.

From: [email protected] (Thomas Pornin)

Organization: Ecole Normale Superieure, Paris

Notwithstanding the problem of knowing the exact size of a type in standard C (you would have 848b12i better luck with unsigned types, by the way), use a dichotomy:

* Returns the least significant bit in the 32-bit value stored in x

* (return value from 0 to 31; 32 if no bit is set)

*/

int least_significant_set_bit(unsigned long x)[1]

if (x & 255UL == 0)

if (x & 15UL == 0)

if (x & 3UL == 0)

if (x & 1UL == 0)

if (!x) t ++;

return t;

For completeness: comp.std.c is about the C standard. Your question would be better addressed in comp.lang.c.[2]

Another participant posted a different version of this algorithm. Here it is:

From: "Douglas A. Gwyn" <[email protected]>

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

comp.lang.c.moderated - moderation address: [email protected]

This is surely an improvement over the first algorithm, since the shifts are gone.

Another answer was the following:

From: Francis Glassborow <[email protected]>

Subject: Re: Most significant bit algorithm

Before giving any guidelines to a solution, note that this was the wrong place to ask, you should have posted to comp.lang.c.moderated.[3]

The answers are likely to be different for the different size types. In addition, some possible 'solutions' are subject knowing the endianess of your system.

For an 8-bit byte, consider masking in the following order:

bits 7 & 0

bits 6 & 1

bits 5 & 2

bits 4 & 3

The first of these to be non-zero tells you that either one or both of the bits you want to locate have been determined. Overall that is likely to provide little advantage over mask each bit and test.

For other types, as long as you know their layout in bytes (unsigned char) use a union to map the value to an array of unsigned char. Now test the individual chars against zero. The highest and lowest non-zero byte can now be tested for the requisite bit. However if you really have a need for maximum efficiency and can sacrifice portability to this end, consider writing an assembler code routine.[4]

Another contribution was:

From: Conor O'Neill <[email protected]>

Organization: Speaking for myself

Least significant bit is fairly easy:

unsigned int least_significant_bit(unsigned int x)[5]

A little bit of playing with examples written out in binary should convince you that it is correct. It even works with x == 0 (i.e., it returns 0). I don't know if there is a similar algorithm for the most significant bit.

I don't either. But it is surely correct I tested it.

Another answer was:

From: "Peter L. Montgomery" <[email protected]>

Organization: CWI, Amsterdam

In article [email protected] () writes:

>Mathew Hendry <[email protected]> wrote:

>>[email protected] wrote:

>>: I need to write an algorithm in C, to [...] determine the least

>In 15 years of programming, I've never had to do anything

>like this. Not once.

>Sure looks to me like y'all did someone's homework for him.

I write number theoretic codes. Locating the rightmost and leftmost significant bits in a nonzero word are two of the 20 or so important primitives needed for more complicated algorithms. If a programming language supports "AND" and "OR" on bits, it should support these primitives too. Alas, few do.

For example, the left-to-right binary method of exponentiation starts with the most significant bit of a number and proceeds downward.

A more complicated example is a binary GCD (greatest common divisor). Assume uint64 is an unsigned 64-bit type:

uint64 GCD(uint64 x, uint64 y)

else

return x1 << nzero;

This short program has five references to a function locating the least significant bit. No wonder that processors such as the Intel Pentium and Alpha 21264 have hardware instructions to locate the rightmost and leftmost significant bits in a word. Optimizing these is much more than homework.

What is the solution in lcc-win32?

Easy:

int getmsb(unsigned int n) /* returns position of most significant bit

int getlsb(unsigned int n) /* returns position of least significant bit

The functions _bsf (bit scan forward) and _bsr (bit scan reverse) are intrinsics. Those functions will be mapped by the compiler directly into assembly, in this case to the machine instructions BSF and BSR that all Intel compatible PCs have. This is extremely efficient, since they will just issue:

bsr eax,eax

The number to be searched will be placed in the eax register by the compiler, and the machine will leave the result in it. This is conceptually the same as calling a function, but takes just a few cycles, depending on the bit pattern of the number.