Date: Sun, 22 Aug 1999 00:44:07 +1000 (EST) From: Patryk Zadarnowski <patryk@ilion.eu.org> To: Nick Hibma <hibma@skylink.it> Cc: hackers@FreeBSD.ORG Subject: Re: from number to power of two Message-ID: <199908211444.AAA68174@mycenae.ilion.eu.org> In-Reply-To: Your message of "Sat, 21 Aug 1999 12:54:32 %2B0200." <Pine.BSF.4.10.9908211250310.7595-100000@heidi.plazza.it>
next in thread | previous in thread | raw e-mail | index | archive | help
> 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 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?199908211444.AAA68174>