Path: utzoo!attcan!uunet!husc6!purdue!decwrl!cookie.dec.com!devine
From: devine@cookie.dec.com (Bob Devine)
Newsgroups: comp.lang.c
Subject: Re: I need a fast algorithm
Message-ID: <8811182228.AA02513@decwrl.dec.com>
Date: 18 Nov 88 20:34:00 GMT
Organization: Digital Equipment Corporation
Lines: 66

> 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);
}