From owner-freebsd-hackers  Sat Aug 21  7:30: 5 1999
Delivered-To: freebsd-hackers@freebsd.org
Received: from labinfo.iet.unipi.it (labinfo.iet.unipi.it [131.114.9.5])
	by hub.freebsd.org (Postfix) with SMTP id 9AC1D15008
	for <hackers@FreeBSD.ORG>; Sat, 21 Aug 1999 07:30:03 -0700 (PDT)
	(envelope-from luigi@labinfo.iet.unipi.it)
Received: from localhost (luigi@localhost) by labinfo.iet.unipi.it (8.6.5/8.6.5) id NAA29830; Sat, 21 Aug 1999 13:51:52 +0200
From: Luigi Rizzo <luigi@labinfo.iet.unipi.it>
Message-Id: <199908211151.NAA29830@labinfo.iet.unipi.it>
Subject: Re: from number to power of two
To: hibma@skylink.it
Date: Sat, 21 Aug 1999 13:51:52 +0200 (MET DST)
Cc: hackers@FreeBSD.ORG
In-Reply-To: <Pine.BSF.4.10.9908211250310.7595-100000@heidi.plazza.it> from "Nick Hibma" at Aug 21, 99 12:54:13 pm
X-Mailer: ELM [version 2.4 PL23]
Content-Type: text
Content-Length: 661       
Sender: owner-freebsd-hackers@FreeBSD.ORG
Precedence: bulk
X-Loop: FreeBSD.ORG

> 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.

The kernel uses a 'ffs()' function for that but i seem to remember
that some processors have this one as a machine instruction.  ffs()
is declared in /sys/sys/libkern.h and implemented in /sys/libkern/ffs.c
but maybe there is an assembly version somewherewhich i can't find.

	cheers
	luigi


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