Lösche das niederwertigste Setzbit

Question

Ich möchte das niedrigstwertige Setzbit eines beliebigen Bits löschen. Das Problem ist, dass ich nicht unbedingt die Num Instanz habe, also x.&.(x-1) ist keine Option. Die einzige Funktion, die ich denken konnte, ist dies:

clearLsb x = x `clearBit` countTrailingZeros x 

ich es gegen die x&(x-1) Version gebenchmarkt, und es ist 1,5 langsamer auf Word32 und Word64 unabhängig von der Höhe der Optimierung. Ich würde mich freuen, wenn jemand einen cleveren Hack dafür kennt.

Answer 1

können Sie überlasten die Funktion die effizientere Umsetzung auf der Typebene, wählen, wenn es verfügbar ist. Dazu muss eine Typklasse hinzugefügt werden, aber selbst mit der countTrailingZeros Implementierung müssen Sie bereits einige Typklassenbeschränkungen für Ihre Funktion definieren (nämlich FiniteBits) ⁽¹⁾.

Insbesondere mit einigen Spracherweiterungen, alle Num Typen können eingestellt a .&. (a - 1) Gleichung verwenden ⁽²⁾:

{-# 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 

---

<sub>1. beachten Sie auch tun, mit countTrailingZeros Sie Ausschluss Integer Typ, das ist countTrailingZeros (16 :: Integer) wird nicht Typ überprüfen, da es keine Instanz von FiniteBits ist.
2. Obwohl wäre besser, explizit Instanzen zu schreiben, als diese Erweiterungen Sprache verwendet</sub>