Re: [PATCH] Add a rounddown_pow_of_two() macro to log2.h.

[Kyle Moffett]

On Jan 26, 2007, at 02:24:35, Robert P. J. Day wrote:
> On Thu, 25 Jan 2007, Andrew Morton wrote:
> > On Thu, 25 Jan 2007 04:32:12 -0500 (EST)
> > "Robert P. J. Day" <rpjday@xxxxxxxxxxxxxx> wrote:
> > > +/*
> > > + * round down to nearest power of two
> > > + */
> > > +static inline __attribute__((const))
> > > +unsigned long __rounddown_pow_of_two(unsigned long n)
> > > +{
> > > +	return 1UL << (fls_long(n) - 1);
> > > +}
> >
> > So __rounddown_pow_of_two(16) returns 8?
>
> it does?  but if that was true, so would 17, and 18, and 19 ...  i  
> didn't actually test this since it seemed so straightforward.  
> doesn't fls_long() return the most significant bit?  oh, wait ...  
> reading further ...

The way that "ilog2" is defined this should be really  
straightforward, I dunno why those functions seem so
overly complicated:
  roundup_pow_of_two(x) := 1 << ilog2(2*x - 1)
  rounddown_pow_of_two(x) := 1 << ilog2(x)

Where ilog2(x) simply returns the first bit set in the word:
  ilog2(0) => undefined or -1 or something
  ilog2(1) => 0
  ilog2(2) => 1
  ilog2(3) => 1
  ilog2(4) => 2
  [...]

The results:
  roundup_pow_of_two(1) = 1    rounddown_pow_of_two(1) = 1
  roundup_pow_of_two(2) = 2    rounddown_pow_of_two(2) = 2
  roundup_pow_of_two(3) = 4    rounddown_pow_of_two(3) = 2
  roundup_pow_of_two(4) = 4    rounddown_pow_of_two(4) = 4
  roundup_pow_of_two(5) = 8    rounddown_pow_of_two(5) = 4
  [...]

Cheers,
Kyle Moffett

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/