From owner-freebsd-hackers  Sat Aug 21  7:45:39 1999
Delivered-To: freebsd-hackers@freebsd.org
Received: from mycenae.ilion.eu.org (mycenae.ilion.eu.org [203.35.206.129])
	by hub.freebsd.org (Postfix) with ESMTP id 27FE115008
	for <hackers@FreeBSD.ORG>; Sat, 21 Aug 1999 07:45:29 -0700 (PDT)
	(envelope-from patryk@ilion.eu.org)
Received: (from patrykz@localhost)
	by mycenae.ilion.eu.org (8.9.3/8.9.3) id AAA68174;
	Sun, 22 Aug 1999 00:44:07 +1000 (EST)
	(envelope-from patryk@ilion.eu.org)
Date: Sun, 22 Aug 1999 00:44:07 +1000 (EST)
Message-Id: <199908211444.AAA68174@mycenae.ilion.eu.org>
X-Authentication-Warning: mycenae.ilion.eu.org: patrykz set sender to patryk@ilion.eu.org using -f
From: Patryk Zadarnowski <patryk@ilion.eu.org>
To: Nick Hibma <hibma@skylink.it>
Cc: hackers@FreeBSD.ORG
Subject: Re: from number to power of two 
In-reply-to: Your message of "Sat, 21 Aug 1999 12:54:32 +0200."
             <Pine.BSF.4.10.9908211250310.7595-100000@heidi.plazza.it> 
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.

Nick,

Probably the  best solution I can think  of is a binary  search on the
number. I'd estimate it as better  than a table, as you save on memory
references (tables sound cool, but, from experience, they cause enough
extra   data   cache  misses   to   kill   any   advantage,  even   in
a highly-optimized inner loop.

For 8-bit integets, a quick solution is:

int
round_up(int x)
{
    if (x & 0xf0) {
	if (x & 0xc0)
	    return (x & 0x80) ? 0x80 : 0x40;
	else {
	    return (x & 0x20) ? 0x20 : 0x10;
	}
    }
    else {
	if (x & 0xc)
	    return (x & 0x8) ? 0x8 : 0x4;
	else {
	    return (x & 0x2) ? 0x2 : 0x1;
	}
    }
}

It's actually faster  than the BSF/BSR operations on  Pentium (and the
ffs() libc function),  as Pentium does a sequential  search of the bit
string and therefore is O(n)  (eek!)  

The innermost comparison could probably  be avoided if it wasn't 00:37
or if  I didn't have to  get up early  in the morning. You  could also
combine  that with  a smaller  lookup table  to get  the best  of both
worlds.

Patryk.


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