Date: Sat, 21 Aug 1999 15:22:20 -0700 From: John-Mark Gurney <gurney_j@efn.org> To: Nick Hibma <hibma@skylink.it> Cc: FreeBSD Hackers mailing list <hackers@FreeBSD.ORG> Subject: Re: from number to power of two Message-ID: <19990821152220.30704@hydrogen.fircrest.net> In-Reply-To: <Pine.BSF.4.10.9908211250310.7595-100000@heidi.plazza.it>; from Nick Hibma on Sat, Aug 21, 1999 at 12:54:32PM %2B0200 References: <Pine.BSF.4.10.9908211250310.7595-100000@heidi.plazza.it>
next in thread | previous in thread | raw e-mail | index | archive | help
Nick Hibma scribbled this message on Aug 21:
> 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.
hmmm.... how about:
int
fls(int n)
{
/* courtesy of fortune, of course this is O(lgn) */
/* swap the bits around */
n = ((n >> 1) & 0x55555555) | ((n << 1) & 0xaaaaaaaa);
n = ((n >> 2) & 0x33333333) | ((n << 2) & 0xcccccccc);
n = ((n >> 4) & 0x0f0f0f0f) | ((n << 4) & 0xf0f0f0f0);
n = ((n >> 8) & 0x00ff00ff) | ((n << 8) & 0xff00ff00);
n = ((n >> 16) & 0x0000ffff) | ((n << 16) & 0xffff0000);
/* mask all but the lowest bit off */
n = n & -n;
/* swap them back to where they were originally */
n = ((n >> 1) & 0x55555555) | ((n << 1) & 0xaaaaaaaa);
n = ((n >> 2) & 0x33333333) | ((n << 2) & 0xcccccccc);
n = ((n >> 4) & 0x0f0f0f0f) | ((n << 4) & 0xf0f0f0f0);
n = ((n >> 8) & 0x00ff00ff) | ((n << 8) & 0xff00ff00);
n = ((n >> 16) & 0x0000ffff) | ((n << 16) & 0xffff0000);
return n;
}
now this is O(lgn) (where n is number of bits in an int), but I'm not
sure how this will perform wrt the other posting.. it probably won't be
that fast because of all the arithmetic that happens, and a binary search
of the number would probably be faster (which I have implemented a few
times)...
--
John-Mark Gurney Voice: +1 541 684 8449
Cu Networking P.O. Box 5693, 97405
"The soul contains in itself the event that shall presently befall it.
The event is only the actualizing of its thought." -- Ralph Waldo Emerson
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?19990821152220.30704>