Date: Mon, 23 Aug 1999 05:01:57 +0800 From: Peter Wemm <peter@netplex.com.au> To: Peter Dufault <dufault@hda.com> Cc: hibma@skylink.it, hackers@FreeBSD.ORG Subject: Re: from number to power of two Message-ID: <19990822210157.C2BA11C1F@overcee.netplex.com.au> In-Reply-To: Your message of "Sun, 22 Aug 1999 09:14:26 -0400." <199908221314.JAA18225@hda.hda.com>
next in thread | previous in thread | raw e-mail | index | archive | help
Peter Dufault wrote:
> > It seems that all the solutions are too generic and slow. As I only have
> > to check the numbers 0-32 (actually 1-32), a block of if statements is
> > almost as fast as a table look up in 33 elements.
>
> I doubt it - use the table for a small fixed size set then
> use Warner's "(n) ? (1 << (ffs(n) - 1)) : 0".
> The possible inline ffs is in machine/cpufunc.h
>
> ffs() is fundamental to scheduling queues and cryptography and
> should have attention paid to it. As Warner said, it could be
> a single instruction on some architectures.
ffs() works from the wrong direction though. He needs the MSB, not the LSB.
There is a fls() inline in <machine/cpufunc.h> though, at least for the x86
family which I think will return the bit number (range: 32 - 1) of the MSB.
So, to get the rounded down (and up) power-of-two value you'd do:
#include <sys/types.h>
#include <machine/cpufunc.h>
#include <stdio.h>
main()
{
int i, down, up;
for (i = 0; i < 65; i++) {
down = i ? (1 << (fls(i) - 1)) : 0;
up = 1 << fls(i);
printf("%d %d %d\n", i, down, up);
}
}
I'm not sure what you want at zero, but the result is:
0 0 1
1 1 2
2 2 4
3 2 4
4 4 8
5 4 8
6 4 8
7 4 8
8 8 16
9 8 16
10 8 16
11 8 16
12 8 16
13 8 16
14 8 16
15 8 16
16 16 32
17 16 32
The << is normally implemented as a barrel shift on most modern CPU's.
The other key trick is (x) & -(x). That returns the LSB in position, not
the bit number.
ie: 12 & -12 =
00001100
& 11110100 (twos complement, in byte form)
= 00000100 = 4 = the value of the LSB.
Cheers,
-Peter
--
Peter Wemm - peter@FreeBSD.org; peter@yahoo-inc.com; peter@netplex.com.au
To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-hackers" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?19990822210157.C2BA11C1F>