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 |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
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 #
From | Date | Subject | |
---|---|---|---|
Next Message | Tom Lane | 2000-07-30 14:53:41 | Re: Problem with updating system indices. |
Previous Message | Michael Robinson | 2000-07-30 08:51:42 | Re: in |