[PROPOSAL] Add `FiniteBits(count{Leading,Trailing}Zeros)`

Herbert Valerio Riedel hvr at gnu.org
Fri Aug 15 08:22:38 UTC 2014

Hello *,

As GHC 7.10.1 will have support for new assembler-optimized CLZ & CTZ[1]
primops[2], it'd be useful to provide also a convenient high-level
interface to avoid having to work with -XMagicHash and unboxed values.

To this end, I hereby propose to add two new methods to the 'FiniteBits'
class, specifically

  class Bits b => FiniteBits b where
    {- ... -}

    countLeadingZeros :: b -> Int
    countLeadingZeros x = (w-1) - go (w-1)
        go i | i < 0       = i -- no bit set
             | testBit x i = i
             | otherwise   = go (i-1)

        w = finiteBitSize x

    countTrailingZeros :: b -> Int
    countTrailingZeros x = go 0
        go i | i >= w      = i
             | testBit x i = i
             | otherwise   = go (i+1)

        w = finiteBitSize x

The full patch (including Haddock doc-strings) is available for code
review at


I suggest to try to keep the discussion/voting/bikeshedding about the
proposal proper here (including any bike-shedding about naming). At same
time, I'd like to invite you to try out the Phab code-revision tool[3]
for pointing-out/discussing technical issues with the proposed patch.


 [1]: http://en.wikipedia.org/wiki/Find_first_set provides a good
      overview why CLZ/CTZ are desirable primitive operations.

 [2]: http://git.haskell.org/ghc.git/commit/e0c1767d0ea8d12e0a4badf43682a08784e379c6

 [3]: Phab code-revisions allow you to directly annotate code-fragments.
      However, after having written inline annotations, you have to actually
      submit those by submitting a non-inline (possibly empty) comment
      (see bottom of that page) to make them visible for everyone.

More information about the Libraries mailing list