From owner-freebsd-hackers Sat Aug 21 15:25:21 1999 Delivered-To: freebsd-hackers@freebsd.org Received: from metriclient-1.uoregon.edu (metriclient-1.uoregon.edu [128.223.172.1]) by hub.freebsd.org (Postfix) with ESMTP id D984514D11 for ; Sat, 21 Aug 1999 15:25:17 -0700 (PDT) (envelope-from gurney_j@efn.org) Received: (from jmg@localhost) by metriclient-1.uoregon.edu (8.9.1/8.8.7) id PAA28405; Sat, 21 Aug 1999 15:22:20 -0700 (PDT) Message-ID: <19990821152220.30704@hydrogen.fircrest.net> Date: Sat, 21 Aug 1999 15:22:20 -0700 From: John-Mark Gurney To: Nick Hibma Cc: FreeBSD Hackers mailing list Subject: Re: from number to power of two References: Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Mailer: Mutt 0.69 In-Reply-To: ; from Nick Hibma on Sat, Aug 21, 1999 at 12:54:32PM +0200 Reply-To: John-Mark Gurney Organization: Cu Networking X-Operating-System: FreeBSD 3.0-RELEASE i386 X-PGP-Fingerprint: B7 EC EF F8 AE ED A7 31 96 7A 22 B3 D8 56 36 F4 X-Files: The truth is out there X-URL: http://resnet.uoregon.edu/~gurney_j/ Sender: owner-freebsd-hackers@FreeBSD.ORG Precedence: bulk X-Loop: FreeBSD.ORG 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