I need a fast algorithm (repost)
Beuning
bgb at ihlpg.ATT.COM
Wed Nov 16 10:35:04 AEST 1988
> 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
More information about the Comp.lang.c
mailing list