Sommaire |
I d like to clear the least significant set bit of an arbitrary Bits type. The problem is, that I do not necessarily have the Num instance, so x.&.(x-1) is not an option. The only function I could think of is this:
clearLsb x = x `clearBit` countTrailingZeros x
I benchmarked it against the x&(x-1) version, and it is 1.5 slower on Word32 and Word64 regardless of the level of optimization. I would appreciate if anyone knows some clever hack to do it.
http://hackage.haskell.org/package/base-4.9.0.0/docs/Data-Bits.html#t:FiniteBits http://hackage.haskell.org/package/base-4.9.0.0/docs/Data-Bits.html#t:FiniteBits
In particular, with some language extensions, all Num types can set to use a .&. (a - 1) equation(2):
{-# LANGUAGE FlexibleInstances, UndecidableInstances #-}
import Data.Bits (Bits, (.&.))
class LSB a where
clear :: a -> a
instance (Bits a, Num a) => LSB a where
clear a = a .&. (a - 1) -- more efficient implementation
newtype Foo = ... -- some type not instance of Num
instance LSB Foo where
clear a = ... -- some other approach
1. do also note that with countTrailingZeros you are ruling out Integer type, that is countTrailingZeros (16 :: Integer) will not type check, since it is not an instance of FiniteBits.
2. Though would be better to write explicit instances than use those language extensions
License : cc by-sa 3.0
http://stackoverflow.com/questions/38173219/clear-the-least-significant-set-bit
