Date: Sun, 22 Aug 1999 21:57:14 -0400 From: Bakul Shah <bakul@torrentnet.com> To: hibma@skylink.it Cc: hackers@FreeBSD.ORG Subject: Re: from number to power of two Message-ID: <199908230157.VAA12466@chai.torrentnet.com>
next in thread | raw e-mail | index | archive | help
The best I can come up with is this:
/* k k+1 k
* given n, return 2 such that 2 > n >= 2
*/
inline unsigned long
n2power2(unsigned long n)
{
/* `smear' the highest set bit to the right */
n |= n>>1; n |= n>>2; n |= n>>4; n |= n>>8; n |= n>>16;
/* now n is of the form 0..01..1 */
return n & ~(n>>1);
}
Note that n bit shift is also O(n) on many machines but
usually a machine instruction implements it so this may still
be faster than 5 or 6 compares and branches that you would
need if a binary search was used. But
n ? 1 << (fls(n)-1) : 0
where fls is inlined may still beat it!
-- bakul
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?199908230157.VAA12466>