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

Re: Off topic 'C' question

From: Mike Mascari <mascarm(at)mascari(dot)com>
To: Alfred Perlstein <bright(at)wintelcom(dot)net>
Cc: pgsql-hackers(at)postgresql(dot)org, hstenger(at)ieee(dot)org
Subject: Re: Off topic 'C' question
Date: 2000-07-30 05:05:51
Message-ID: 3983B7AF.709E30C5@mascari.com (view raw or flat)
Thread:
Lists: pgsql-hackers
Alfred Perlstein wrote:
> 
> * Mike Mascari <mascarm(at)mascari(dot)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

In response to

pgsql-hackers by date

Next:From: Denis PerchineDate: 2000-07-30 08:18:26
Subject: Problem with updating system indices.
Previous:From: Alfred PerlsteinDate: 2000-07-30 03:26:22
Subject: Re: Off topic 'C' question

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