From owner-freebsd-hackers Sun Aug 22 6:39:51 1999 Delivered-To: freebsd-hackers@freebsd.org Received: from web108.yahoomail.com (web108.yahoomail.com [205.180.60.75]) by hub.freebsd.org (Postfix) with SMTP id A40EC154EA for ; Sun, 22 Aug 1999 06:39:43 -0700 (PDT) (envelope-from thallgren@yahoo.com) Message-ID: <19990822133841.9871.rocketmail@web108.yahoomail.com> Received: from [195.100.253.159] by web108.yahoomail.com; Sun, 22 Aug 1999 06:38:41 PDT Date: Sun, 22 Aug 1999 06:38:41 -0700 (PDT) From: =?iso-8859-1?q?Tommy=20Hallgren?= Subject: Re: from number to power of two To: mit@mit-s.otaru-uc.ac.jp, hackers@FreeBSD.ORG MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit Sender: owner-freebsd-hackers@FreeBSD.ORG Precedence: bulk X-Loop: FreeBSD.ORG --- Kazufumi-MIT-Mitani skrev: > "Daniel C. Sobral" wrote > > > That technique is O(ln(n)), where n is the number in question. > > > > Frankly, for numbers up to 32, a table will wield the best results, > > and might actually be smaller than some of the suggestions given so > > far. > > Counting n as bit, it is O(n) :p No it isn't. You're only looping a maximum of 32 times, not 2^32 times. > Unrolling the loop, > > if(n<=2^0) 2^0 > else if(n<=2^1) 2^1 > else if(n<=2^2) 2^2 > else if(n<=2^3) 2^3 > : > : > else if(n<=2^31) 2^31 > > is suitable for this problem? IMHO, the best solution so far, if a lookup table isn't suitable, is the binary search version that someone posted. Regards, Tommy === Tommy Hallgren Briljantg. 31, SE-421 49, Göteborg Tel.: 0709 - 312 404 (GSM) Tel.: 031 - 47 65 28 (Home) __________________________________________________ Do You Yahoo!? Bid and sell for free at http://auctions.yahoo.com To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-hackers" in the body of the message