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>