I need a fast algorithm
Bob Devine
devine at cookie.dec.com
Sat Nov 19 06:34:00 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.
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);
}
More information about the Comp.lang.c
mailing list