Re: Off topic 'C' question

Mike Mascari wrote:
> I have a quick question. What is the quickest way to determine
> the next highest power of two which is greater than a given
> integer in 'C'. For example, given the number 7, I would like to
> return 8. Given the number 13, I would like to return 16, etc. Is
> there a gem to do this without shifting a bit value from 1 left
> up to a maximum of 32 (or 64) iterations?

Binary search.
   I   assumed   you   really   mean   greater   than,  so  that   next_power2(4096) is 8192.
   For 32 bit values, the function
       unsigned int next_power2_32 (unsigned int value)       {           unsigned int comp = 1 << 16;
unsignedint off  = 8;
 
           if (value == 0)               return 1;
           while (off > 0 && comp != value)           {               if (comp > value)                   comp >>= off;
             else                   comp <<= off;
 
               off >>= 1;           }
           if (comp <= value)               comp <<= 1;           return comp;       }
   is guaranteed to have at maximum 4 loop  iterations  for  any   value  you want. Should be polished up a little for
values>=   (1 << 31), but I leave that to you. Obviuosly, looking for 64   bit  numbers,  the  loop max would be 5, and
whenwe have 256   bit integers as standard (in approx.   5-6  years  :-)  it'll   finish with 7 iterations.
 


Jan

--

#======================================================================#
# It's easier to get forgiveness for being wrong than for being right. #
# Let's break this rule - forgive me.                                  #
#================================================== JanWieck@Yahoo.com #