Skip site navigation (1) Skip section navigation (2)

Re: Off topic 'C' question

From: JanWieck(at)t-online(dot)de (Jan Wieck)
To: Mike Mascari <mascarm(at)mascari(dot)com>
Cc: pgsql-hackers(at)postgresql(dot)org
Subject: Re: Off topic 'C' question
Date: 2000-07-30 11:28:38
Message-ID: 200007301128.NAA06482@hot.jw.home (view raw or flat)
Thread:
Lists: pgsql-hackers
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(at)Yahoo(dot)com #



In response to

pgsql-hackers by date

Next:From: Tom LaneDate: 2000-07-30 14:53:41
Subject: Re: Problem with updating system indices.
Previous:From: Michael RobinsonDate: 2000-07-30 08:51:42
Subject: Re: in

Privacy Policy | About PostgreSQL
Copyright © 1996-2014 The PostgreSQL Global Development Group