CODEWITHSUNDEEP
haskellbit-manipulation
lanskey
lanskey

Reputation: 457

Clear the least significant set bit

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.

Upvotes: 3

Views: 401

Answers (1)

behzad.nouri
behzad.nouri

Reputation: 77941

You may overload the function to pick the more efficient implementation at the type level, when it is available. This requires adding a type class, but even with countTrailingZeros implementation you already have to impose some type-class constraint to your function (namely FiniteBits) (1).

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

Upvotes: 3

Related Questions