[Is bitstr.h used in the kernel?  Or is this off-topic?  If so, I apologize.]

I see that Chapman already indicated that x&(-x) was what was in 
mind.  This can be written more or less correctly for either 1s or 2s 
complement as x&(~x+1), provided that x is really unsigned and that 
~x works properly for negative zero and positive zero.  [There's no 
wrap around carry unless x is true zero, since ~x is therefore less 
than 0xFFFFFF...FFF, but (0 & anything) is still zero even on a 1s 
complement machine.  So ~x+1 is the same as twos complement negation of x.]

Since bitstr_t is unsigned char, one can readily use a table
         extern const sint8_t fliplog2[256];
The values of this table then directly give the value you want (log 2 
of the bit-reversed byte), and -1 for a zero byte.  Then you just 
have to scan the array.

Opinions will vary as to whether (on modern hardware) this really 
speeds things up, as the fliplog2[] table entry that's needed will 
often not be in the D-cache, whereas the instructions for the spin in 
the for-loop will be in the I-cache.  (I once heard someone say, 
sarcastically, that hyperthreading was invented because somebody 
wanted to put to work the power they were wasting clocking the whole 
core while waiting for cache lines to fill....)

There are lots of approaches to implementing this function; scan for 
a non-zero word, etc.  The problem is that in a general package like 
<bitstring.h> it's hard to do the intelligent thing, which is to look 
for the most likely first set bit.  In most performance-sensitive 
problems, a clever renumbering of bits can help; in cases where the 
table is really sparse, you'd want to search using very wide loads 
looking for non-zero bitmaps, then narrow down.  But <bitstring.h> 
doesn't know the use cases, and so has to be coded in a way that is 
not going to be very satisfactory in many cases.

Therefore, I suspect that people using <bitstring.h> are probably 
using it for convenience/clarity and are not likely to be terribly 
concerned about performance.

(I also suspect that I'm about to be corrected again; good for the soul.)

--Terry

At 06:23 PM 1/6/2006 -0800, Bill Studenmund wrote:

>*** PGP SIGNATURE VERIFICATION ***
>*** Status:   Good Signature from Invalid Key
>*** Alert:    Please verify signer's key before trusting signature.
>*** Signer:   William R. Studenmund (NetBSD Devel) 
><wrstuden@netbsd.org> (0x751C8BD7)
>*** Signed:   1/6/2006 9:23:49 PM
>*** Verified: 1/6/2006 11:44:22 PM
>*** BEGIN PGP VERIFIED MESSAGE ***
>
>On Fri, Jan 06, 2006 at 08:52:25PM -0500, Chapman Flack wrote:
> > Rui Paulo wrote:
> > >On 2006.01.06 14:06:54 -0500, Chapman Flack wrote:
> > >| Are there any current or contemplated NetBSD ports to
> > >| non-2s-complement machines?
> > >
> > >No, I don't think so.
> >
> > ok ... I wondered because I wasn't sure why bit_ffs in bitstring(3) is
> > done with a per-bit for loop, and thought maybe it meant 2s complement
> > techniques would be making too much of an architecture assumption.
> > Does anyone know of a reason not to use x^(x-1) in NetBSD code?
>
>Because I don't see how x^(x-1) will give you the first bit set. :-)
>
>I've tried plugging in some numbers, and I don't see how we can use
>exclusive-or math instead of a for loop. I do see how we could make it
>O(log # bits in byte), but that's O(8) vs O(3)...
>
>Take care,
>
>Bill
>
>
>*** END PGP VERIFIED MESSAGE ***