Date: Sun, 22 Aug 1999 06:38:41 -0700 (PDT) From: =?iso-8859-1?q?Tommy=20Hallgren?= <thallgren@yahoo.com> To: mit@mit-s.otaru-uc.ac.jp, hackers@FreeBSD.ORG Subject: Re: from number to power of two Message-ID: <19990822133841.9871.rocketmail@web108.yahoomail.com>
next in thread | raw e-mail | index | archive | help
--- Kazufumi-MIT-Mitani <mit@mit-s.otaru-uc.ac.jp> skrev: > "Daniel C. Sobral" <dcs@newsguy.com> 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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?19990822133841.9871.rocketmail>