4 Dec
2007
4 Dec
'07
5:29 a.m.
On Dec 3, 2007 9:10 PM, Don Stewart
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