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