[comp.lang.c] I need a fast algorithm

bgb@ihlpg.ATT.COM (Beuning) (11/16/88)

> 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

devine@cookie.dec.com (Bob Devine) (11/19/88)

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

  Ok, I wasn't going to start inventing better algorithms.  But the 
two replies I saw to the request generated incorrect results.  Sooooo...
Here are two suggestions.  Both are faster than the original.

  I can't think of a O(1) algorithm to perform the request.  Sorry.

  Note that I assumed that ints are 32 bits in the first version.
You mean all the world isn't a VAX? ;-)

Bob
==============

/* about 10% faster than the initial method */
/* average number of iteration == 8 */
/* setup cost   = compare, assign, branch */
/* loop cost    = and, compare, shift, compare, branch */
/* cleanup cost = subtract, compare, [shift], assign */
unsigned int
al(size)
    register unsigned int size;
{                           
    register unsigned int pow_of_two;
	
    if (size < 1<<16)
        pow_of_two = 1<<15;
    else
	pow_of_two = 1<<31;

    do {
	if (size & pow_of_two)
	    return( (size-pow_of_two) ? pow_of_two<<=1 : pow_of_two);
    } while (pow_of_two>>=1);

    return(1);
}

/* about 30% faster than the initial method; faster for small numbers */
/* average number of iteration == hard to tell, depends on size of input */
/* setup cost   = compare, branch, assign */
/* loop cost    = shift, compare, branch, or */
/* cleanup cost = add, shift, compare, branch, assign */
unsigned int
al(size)
register unsigned int size;
{                
    register unsigned int tmp;
    register unsigned int hi_bit = size;
    
    /* the special case of 0 slows every case */
    if (size == 0)
        return(1);

    /* from the first bit to lowest, make sure they are set */
    /* if you have large numbers on average, can speed up   */
    /*  - by setting more than one bit at a time */
    for (tmp = size; tmp >>= 1;	hi_bit |= tmp)
	continue;

    if ((++hi_bit >> 1) == size)
        return(size);
    else
        return(hi_bit);
}