From owner-freebsd-hackers  Sun Aug 22 18:57:29 1999
Delivered-To: freebsd-hackers@freebsd.org
Received: from chai.torrentnet.com (chai.torrentnet.com [198.78.51.73])
	by hub.freebsd.org (Postfix) with ESMTP id 3C723153FD
	for <hackers@FreeBSD.ORG>; Sun, 22 Aug 1999 18:57:17 -0700 (PDT)
	(envelope-from bakul@torrentnet.com)
Received: from chai.torrentnet.com (localhost [127.0.0.1])
	by chai.torrentnet.com (8.8.8/8.8.5) with ESMTP id VAA12466;
	Sun, 22 Aug 1999 21:57:14 -0400 (EDT)
Message-Id: <199908230157.VAA12466@chai.torrentnet.com>
To: hibma@skylink.it
Cc: hackers@FreeBSD.ORG
Subject: Re: from number to power of two 
Date: Sun, 22 Aug 1999 21:57:14 -0400
From: Bakul Shah <bakul@torrentnet.com>
Sender: owner-freebsd-hackers@FreeBSD.ORG
Precedence: bulk
X-Loop: FreeBSD.ORG

The best I can come up with is this:

/*                  k            k+1         k
 * given n, return 2  such that 2    > n >= 2
 */
inline unsigned long
n2power2(unsigned long n)
{
	/* `smear' the highest set bit to the right */
	n |= n>>1; n |= n>>2; n |= n>>4; n |= n>>8; n |= n>>16;
	/* now n is of the form 0..01..1 */
	return n & ~(n>>1);
}

Note that n bit shift is also O(n) on many machines but
usually a machine instruction implements it so this may still
be faster than 5 or 6 compares and branches that you would
need if a binary search was used.  But
	n ? 1 << (fls(n)-1) : 0
where fls is inlined may still beat it!

-- bakul


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