prm@aplvax.jhuapl.edu (Paul Raymond McMullin) (11/15/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 >> al(2) -> 2 >> al(13) -> 16 >> al(32) -> 32 >> al(257) -> 512 >> >>etc. > >Here's my shot at it ... > > unsigned int > al(size) > register unsigned int size; > { > register unsigned int try = 1; > > while (try > 0 && size > try) { > try <<= 1; > } > > return (try); > } > >This works and returns 0 if there is no power of 2 greater than the >argument. But is there something that is faster? How about something >involving a series of boolean operations? > >-- > Lloyd Zusman, Master Byte Software, Los Gatos, California "fast" takes a strange meaning here... if you expect most of your inputs to this function to be "near" zero, the above function will probably be pretty good, taking 4 or five instructions (in the loop) per power of two contained in the answer. If your inputs to the function are distributed uniformly between 0 and 2**31 (assuming a thirty-two bit word), you might try something like: unsigned int al(size) register unsigned int size; { register unsigned int try; try = 1; if (size > 1<<16) { /* change 'if' to 'while' for more */ size =size>>16; /* portable code to handle bigger */ try = try<<16; /* wordsizes in a timely fashion */ } if (size > 1<<8) { /* here and below, size < 2**16 */ size = size >> 8; try = try << 8; } if (size > 1<<4) { /* here and below, size < 2**8 */ size = size >> 4; try = try << 4; } if (size > 1<<2) { /* here and below, size < 2**4 */ size = size >> 2; try = try << 2; } if (size > 1<<1) { /* here and below, size < 2**2 */ size = size >> 1; try = try << 1; } if (size) /* here size < 2 */ try = try << 1; return try; } notice that I've assumed that your compiler was smart enough to "constant fold" the shifted ones in the comparisons -- for a stupid compiler you may have to do this by replacing them yourself. Also, notice that if your int sizes are longer than 32 bits you can either add aditional cascades (e.g. "if (size > 1<<32)" etc, or change the first cascade into a while loop (which will make it portable to *any* length integers, loping off 16 bits at a time for *really big* numbers. I've tested the program for the examples you gave above, but I didn't try MAXINT (or 2**31 either).. I suspect that it'll return 0 for MAXINT like the other suggested algorithm, but haven't bothered to try it... I don't fool with unsigned numbers that much. The program would be more clearly defined for the MAXINT case if you were asking for the power of two that contains the argument: you would initialize try to zero, and change all of the try = try << x statements to try += x statements. It seems to me that what you should want for al(1) is 1, not two! (You seem to have forgotten that 2**0 is 1.) Fixing this case doesn't appear trivial at first, I'll leave it as an exercise for the reader... I'm not sure why you defined al(0) to return 1 when al(2) returns 2; it seems to me that al(0) should be 0! If you change your mind, you'll have to handle the MAXINT case better, and add "else return 0;" as a completion for the "if (size) try = try<<1" statement. Looking back over my code, it'll probably take 2 instructions per comparison that fails (e.g. small numbers falling through the first few cascades), and 4 instructions for each cascade that passes (two for the comparisons and two shifts), so for all but the cases where size < 32 my code will probably beat the first suggested implementation for speed.