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

[Don Stewart]

dpiponi:
> 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.

Yes, perhaps look into what GMP provides, then bind to it, and call it
on the underlying ByteArray#

-- Don