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? 

Thanks for any info, 

Mike Mascari

Sat, 29 Jul 2000 21:38:33 -0400
Mike Mascari <mascarm@mascari.com>
Off topic 'C' question
* Mike Mascari <mascarm@mascari.com> [000729 18:40] 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? 
> 
> Thanks for any info, 

Think "binary search".

-Alfred

Sat, 29 Jul 2000 20:26:22 -0700
Alfred Perlstein <bright@wintelcom.net>
Re: Off topic 'C' question
Alfred Perlstein wrote:
> 
> * Mike Mascari <mascarm@mascari.com> [000729 18:40] 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?
> >
> > Thanks for any info,
> 
> Think "binary search".
> 
> -Alfred

Yeah. Start with 2^16, check if larger. If so, check 2^8, etc. In
Graphics Gems II, there's an algorithm by Ken Shoemake for
finding the lowest 1-bit set. You take the bit-wise AND of the
word and its negative -- that easy. I was hoping something
similar existed for finding the highest bit set. If so, I could
just shift the result left one. If not, if there's a way to flip
the bits in an unsigned integer without barrel shifting, then all
I would have to do is:

flip
take bit-wise AND with negative
flip
shift left 1

The binary search, is of course, better then brute force, but can
be worse than linear for low values. For example, a search for
2^5 would yield:

2^16
2^0
2^8
2^4
2^6
2^5

or 6 iterations instead of 5, plus the actual shifting of the
search value. I guess I was hoping for some "bit-magic" out
there.

Cheers,

Mike Mascari

Sun, 30 Jul 2000 01:05:51 -0400
Mike Mascari <mascarm@mascari.com>
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;
            unsigned int 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 when we 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 #



Sun, 30 Jul 2000 13:28:38 +0200 (MEST)
JanWieck@t-online.de (Jan Wieck)
Re: Off topic 'C' question
On Sat, Jul 29, 2000 at 09:38:33PM -0400, 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? 

You could use:

pow(x, ((int)(log(x)/log(2)) + 1));

-- 
Louis-David Mitterrand - ldm@apartia.org - http://www.apartia.org

 "Poor girl looks as confused as a blind lesbian in a fish market." -
 Simon R. Green 

Fri, 11 Aug 2000 23:18:23 +0200
Louis-David Mitterrand <cunctator@apartia.ch>
Re: Off topic 'C' question
On Fri, Aug 11, 2000 at 11:18:23PM +0200, Louis-David Mitterrand wrote:
> On Sat, Jul 29, 2000 at 09:38:33PM -0400, 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? 
> 
> You could use:
> 
> pow(x, ((int)(log(x)/log(2)) + 1));

Sorry the correct way is:

    #include <math.h>
    #include <stdio.h>
    #include <stdlib.h>

    int main(int argc, char ** argv) {
        int r = atoi(argv[1]);
        printf("result is %g\n", pow(2, (int)((log(r)/log(2)) + 1)));
        return 0;
    }

This works for any power, simply replace 2 by the desired exponent.

-- 
Louis-David Mitterrand - ldm@apartia.org - http://www.apartia.org

Sat, 12 Aug 2000 08:50:54 +0200
Louis-David Mitterrand <cunctator@apartia.ch>
Re: Re: Off topic 'C' question