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