[Haskell-cafe] Looking for smallest power of 2 >= Integer

[Dan Piponi]

On Dec 3, 2007 9:10 PM, Don Stewart <dons at galois.com> wrote:
> > Is there anything in any of the interfaces to Integer that will allow
> > me to quickly find the highest bit set in an Integer?
> Well, you could use testBit, which is pretty efficient,

But testBit tests only one bit at a time. To prove that i is the
highest bit of n I need to prove that all higher bits are set to zero,
and I can't do that with testBit. The obvious thing is "shiftR n i ==
0" but I'm worried that that entails the wasteful operation of
shifting all of the bits above bit i. Internally the implementation of
Integer must know a good upper bound on where the highest bit is.
Maybe I need to delve into GHC.Prim.
--
Dan