Re: sparse using insane amounts of memory

["Darren Jenkins" <darrenrjenkins-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>]

On 3/9/07, Linus Torvalds <torvalds-de/tnXTf+JLsfHDXvbKv3WD2FQJk+8+b@public.gmane.org> wrote:
>
>
> On Thu, 8 Mar 2007, Linus Torvalds wrote:
> >
> > To check a value for being a nice range of consecutive bits, you can
> > simply do:
> >
> >       #define is_power_of_two(x) (!((x) & ((x)-1)))

There is already an inline for this in log2.h

/*
 *  Determine whether some value is a power of two, where zero is
 * *not* considered a power of two.
 */

static inline __attribute__((const))
bool is_power_of_2(unsigned long n)
{
	return (n != 0 && ((n & (n - 1)) == 0));
}

>  - 0 is special, and is generally considered to be a power of two (and
>    this is more fundamental than you'd think: it's not just fall-out from
>    the particular expression chosen, it is fundamentally *required* to
>    handle overflow, and you can think of 0 as 2**x, x > wordsize if that
>    makes you more comfortable with the notion that zero is a power-of-two
>    in any finite representation of 2's complement)
>
> The "zero is special" thing means that if you don't want to accept zero as
> a valid mask (it technically *is* a contiguous set of bits set - it's just
> the empty set) you'd need to check for it specially.

I guess the person who wrote it wasn't thinking discrete maths at the time.

Darren J.