Skip site navigation (1)
Skip section navigation (2)
## Re: Off topic 'C' question

### In response to

### pgsql-hackers by date

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

- Re: Off topic 'C' question at 2000-07-30 03:26:22 from Alfred Perlstein

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