From owner-freebsd-hackers Sun Aug 22 14: 4: 3 1999 Delivered-To: freebsd-hackers@freebsd.org Received: from overcee.netplex.com.au (overcee.netplex.com.au [202.12.86.7]) by hub.freebsd.org (Postfix) with ESMTP id E7553155FF for ; Sun, 22 Aug 1999 14:03:33 -0700 (PDT) (envelope-from peter@netplex.com.au) Received: from netplex.com.au (localhost [127.0.0.1]) by overcee.netplex.com.au (Postfix) with ESMTP id C2BA11C1F; Mon, 23 Aug 1999 05:01:57 +0800 (WST) (envelope-from peter@netplex.com.au) X-Mailer: exmh version 2.0.2 2/24/98 To: Peter Dufault Cc: hibma@skylink.it, hackers@FreeBSD.ORG Subject: Re: from number to power of two In-reply-to: Your message of "Sun, 22 Aug 1999 09:14:26 -0400." <199908221314.JAA18225@hda.hda.com> Date: Mon, 23 Aug 1999 05:01:57 +0800 From: Peter Wemm Message-Id: <19990822210157.C2BA11C1F@overcee.netplex.com.au> Sender: owner-freebsd-hackers@FreeBSD.ORG Precedence: bulk X-Loop: FreeBSD.ORG 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 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 #include #include 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