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 majord...@freebsd.org
with "unsubscribe freebsd-hackers" in the body of the message
