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 - pe...@freebsd.org; pe...@yahoo-inc.com; pe...@netplex.com.au
To Unsubscribe: send mail to majord...@freebsd.org
with "unsubscribe freebsd-hackers" in the body of the message
