Subject: Re: diff to speed up fdalloc using two-level bitmaps
To: None <tech-perform@netbsd.org>
From: Alan Barrett <apb@cequrux.com>
List: tech-perform
Date: 10/28/2003 23:19:52
On Tue, 28 Oct 2003, Niels Provos wrote:
> An inline assembly function for finding the first zero bit in a
> word would be a great thing to have across architectures.

It's much easier to find the last (that is, least significant) set
or clear bit.  You can sometimes change the algorithm or the data
representation to suit.

    unsigned int find_last_set(unsigned int x)
    {
	return (x & -x);
    }

    unsigned int find_last_clear(unsigned int x)
    {
	return (~x & (x+1));
    }

--apb (Alan Barrett)