Re: Off topic 'C' question

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