From owner-freebsd-hackers  Sun Aug 22  4: 8:15 1999
Delivered-To: freebsd-hackers@freebsd.org
Received: from peach.ocn.ne.jp (peach.ocn.ne.jp [210.145.254.87])
	by hub.freebsd.org (Postfix) with ESMTP id 9A6CC14ED3
	for <hackers@FreeBSD.ORG>; Sun, 22 Aug 1999 04:08:12 -0700 (PDT)
	(envelope-from dcs@newsguy.com)
Received: from newsguy.com by peach.ocn.ne.jp (8.9.1a/OCN) id UAA25673; Sun, 22 Aug 1999 20:07:47 +0900 (JST)
Message-ID: <37BFD9D0.D330B565@newsguy.com>
Date: Sun, 22 Aug 1999 20:06:56 +0900
From: "Daniel C. Sobral" <dcs@newsguy.com>
X-Mailer: Mozilla 4.6 [en] (Win98; I)
X-Accept-Language: en,pt-BR,ja
MIME-Version: 1.0
To: John-Mark Gurney <gurney_j@resnet.uoregon.edu>
Cc: Mark Murray <mark@grondar.za>, Nick Hibma <hibma@skylink.it>,
	FreeBSD Hackers mailing list <hackers@FreeBSD.ORG>
Subject: Re: from number to power of two
References: <199908220750.JAA69064@gratis.grondar.za> <19990822010157.02195@hydrogen.fircrest.net>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Content-Transfer-Encoding: 7bit
Sender: owner-freebsd-hackers@FreeBSD.ORG
Precedence: bulk
X-Loop: FreeBSD.ORG

John-Mark Gurney wrote:
> 
> > Shift a bit until it becomes greater than (or less than) the number
> > in question.
> 
> ummm, didn't you read his post?? he wanted a O(1) routine, NOT a O(n)
> routine...

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.

--
Daniel C. Sobral			(8-DCS)
dcs@newsguy.com
dcs@freebsd.org

	- Come on.
	- Where are we going?
	- To get what you came for.
	- What's that?
	- Me.


To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-hackers" in the body of the message