Path: utzoo!utgpu!watmath!clyde!att!ihlpg!bgb
From: bgb@ihlpg.ATT.COM (Beuning)
Newsgroups: comp.lang.c
Subject: Re: I need a fast algorithm (repost)
Message-ID: <5602@ihlpg.ATT.COM>
Date: 16 Nov 88 00:35:04 GMT
References: <LJZ.88Nov14103934@fxgrp.fx.com>
Organization: AT&T Bell Laboratories - Naperville, Illinois
Lines: 53

> I need a fast algorithm.  I'm looking for the fastest way to get the
> lowest power of two that is greater than or equal to a number.  For
> example, if the function that performs this algorithm is named 'al' ...
> 
> 	al(0)	-> 1
> 	al(1)	-> 2		/* isn't 1 == 2^0 ? */
> 	al(2)	-> 2
> 	al(13)	-> 16
> 	al(32)	-> 32
> 	al(257)	-> 512

Many bit problems can be solved by having an array of answers for
a smaller number of bits and then breaking down the problem so it
can be answered by an array lookup.  Here is an example that only
works for 8-bit input numbers.

short	bit4[ 16 ] = {
	1,	1,	2,	4,
	4,	8,	8,	8,
	8,	16,	16,	16,
	16,	16,	16,	16
};

al( x )
{
	return( (x > 15) ? (bit4[ x >> 4 ] * 16) : bit4[ x ] );
}

If you want speed or a larger range you can fill out the bit[] array
up to 256 (or even 64K) and then with four range checks you can handle
32-bit input numbers

short	bit8[ 256 ] = { 1, 1, 2, 4, ..., 256 };

al( unsigned x )
{
	if( x < 0x10000 ) {
		return( (x < 0x100) ? bit8[ x ] : (bit8[ x >> 8 ] << 8) );
	} else {
		return( (x < 0x1000000)
			? (bit8[ x >> 16 ] << 16)
			: (bit8[ x >> 24 ] << 24) );
	}
}

With a different bit[] array, this same approach works for counting
the number of bits set in a word.


		Hope this helps,

		Brian Beuning
		att!ihlpn!bgb