haskell - 清除最低有效设置位

Question

我想清除任意位类型的最低有效设置位。问题是，我不一定有 Num 实例，因此 x.&.(x-1) 不是一个选项。我能想到的唯一功能是:

clearLsb x = x `clearBit` countTrailingZeros x

我将其与 x&(x-1) 版本进行了基准测试，结果发现，无论级别如何，在 Word32 和 Word64 上它都会慢 1.5 倍的优化。如果有人知道一些聪明的技巧来做到这一点，我将不胜感激。

Answer 1

您可以重载该函数，以便在类型级别选择更有效的实现(如果可用)。这需要添加类型类，但即使使用 countTrailingZeros实现时，您已经必须对您的函数施加一些类型类约束(即 FiniteBits ) ⁽¹⁾。

特别是，通过某些语言扩展，所有 Num 类型都可以设置为使用 a .&。 (a - 1) 方程⁽²⁾:

{-# 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。另请注意，使用 countTrailingZeros 您将排除 Integer 类型，即 countTrailingZeros (16::Integer) 不会 类型检查，因为它不是 FiniteBits 的实例。
2. 虽然编写显式实例比使用这些语言扩展更好