Date: Sat, 21 Aug 1999 14:11:03 -0500 (CDT) From: Don Read <dread@texas.net> To: Nick Hibma <hibma@skylink.it> Cc: FreeBSD Hackers mailing list <hackers@FreeBSD.ORG> Subject: RE: from number to power of two Message-ID: <XFMail.990821141103.dread@texas.net> In-Reply-To: <Pine.BSF.4.10.9908211250310.7595-100000@heidi.plazza.it>
next in thread | previous in thread | raw e-mail | index | archive | help
On 21-Aug-99 Nick Hibma wrote:
>
> 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.
a bit of fiddling around gives:
int pw2(register unsigned i) {
register unsigned cnt=1;
do {
i >>= 1;
cnt <<=1;
/* printf("[%x %x],",i, cnt); */
} while (i);
/* return(cnt) /* higher */
return( cnt >> 1); /* in bound */
/* return(cnt >> 2); /* lower */
}
Prolly should do boundry check for case 0 : 0 -> 0 ? 0 -> 1.
Regards,
---
Don Read dread@calcasieu.com
EDP Manager dread@texas.net
Calcasieu Lumber Co. Austin TX
-- But I'm in good company, sendmail has kicked a great many
butts in the past
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?XFMail.990821141103.dread>