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>