Re: Off topic 'C' question

From: Mike Mascari Alfred Perlstein pgsql-hackers(at)postgresql(dot)org, hstenger(at)ieee(dot)org Re: Off topic 'C' question 2000-07-30 05:05:51 3983B7AF.709E30C5@mascari.com (view raw or whole thread) 2000-07-30 01:38:33 from Mike Mascari  2000-07-30 03:26:22 from Alfred Perlstein   2000-07-30 05:05:51 from Mike Mascari  2000-07-30 11:28:38 from JanWieck(at)t-online(dot)de (Jan Wieck)  2000-08-11 21:18:23 from Louis-David Mitterrand   2000-08-12 06:50:54 from Louis-David Mitterrand 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

```

pgsql-hackers by date

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