> Does anyone know an inexpensive algorithm (O(1)) to go from an number to
> the next (lower or higher) power of two.
>
> 1 -> 1
> 2,3 -> 2
> 4,5,6,7 -> 4
> 8,9,10,11,12,13,14,15 -> 8
> etc.
>
> So %1101 should become either %10000 or %1000.
>
> The only solution I have so far is a table. That is a possibility as the
> the highest number will be 32 I think.
Nick,
Probably the best solution I can think of is a binary search on the
number. I'd estimate it as better than a table, as you save on memory
references (tables sound cool, but, from experience, they cause enough
extra data cache misses to kill any advantage, even in
a highly-optimized inner loop.
For 8-bit integets, a quick solution is:
int
round_up(int x)
{
if (x & 0xf0) {
if (x & 0xc0)
return (x & 0x80) ? 0x80 : 0x40;
else {
return (x & 0x20) ? 0x20 : 0x10;
}
}
else {
if (x & 0xc)
return (x & 0x8) ? 0x8 : 0x4;
else {
return (x & 0x2) ? 0x2 : 0x1;
}
}
}
It's actually faster than the BSF/BSR operations on Pentium (and the
ffs() libc function), as Pentium does a sequential search of the bit
string and therefore is O(n) (eek!)
The innermost comparison could probably be avoided if it wasn't 00:37
or if I didn't have to get up early in the morning. You could also
combine that with a smaller lookup table to get the best of both
worlds.
Patryk.
To Unsubscribe: send mail to majord...@freebsd.org
with "unsubscribe freebsd-hackers" in the body of the message
