Opened 8 years ago

Closed 7 years ago

#3563 closed proposal (wontfix)

A couple of additions to Data.Bits

Reported by: porges Owned by:
Priority: normal Milestone: Not GHC
Component: libraries/base Version: 6.11
Keywords: Cc: merehap@…, gabriel@…
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

Population count is an often-needed function when bitfiddling, so I think a version should be supplied. I also have included functions for converting to and from lists of Booleans:

-- population count
popCount :: (Bits a, Num t) => a -> t
popCount x = count' (bitSize x) x 0
  where
  count' 0 _ acc = acc
  count' n x acc = count' (n-1) (x `shiftR` 1) (acc + if x .&. 1 == 1 then 1 else 0)
                -- this weird if/else is to preserve the nice type signature :)

-- converts a list of bools to a number
fromBools :: (Bits a) => [Bool] -> a
fromBools = foldl' (\i b -> (i `shiftL` 1) .|. if b then 1 else 0) 0 -- likewise

-- converts a number to a list of bools
toBools :: (Bits a) => a -> [Bool]
toBools x = reverse (toBools' (bitSize x) x)
  where
  toBools' 0 _ = []
  toBools' n x = (x .&. 1 == 1) : toBools' (n-1) (x `shiftR` 1)

Change History (5)

comment:1 Changed 8 years ago by igloo

difficulty: Unknown
Milestone: Not GHC

comment:2 Changed 8 years ago by morrow

Type of failure: None/Unknown

I was just doing some bit twiddling the other day, here's some (C -> Haskell) stuff i ended up with:

pop64 :: Word64 -> Int
pop64 x =
  let a = 0x5555555555555555
      b = 0x3333333333333333
      c = 0x0f0f0f0f0f0f0f0f
      d = 0x0101010101010101
  in case x - (x `shiftRL` 1) .&. a of
    x -> case (x .&. b) + ((x `shiftRL` 2) .&. b) of
      x -> case ((x + (x `shiftRL` 4)) .&. c) * d of
        x -> case x `shiftRL` 56 of
          x -> fromIntegral x

bsr64 :: Word64 -> Int
bsr64 x0 =
  case (x0 .|. shiftRL x0 1) of
    x1 -> case (x1 .|. shiftRL x1 2) of
      x2 -> case (x2 .|. shiftRL x2 4) of
        x3 -> case (x3 .|. shiftRL x3 8) of
          x4 -> case (x4 .|. shiftRL x4 16) of
            x5 -> case (x5 .|. shiftRL x5 32) of
              x6 -> case pop64 x6 - 1 of
                x -> fromIntegral x

-- from Data.IntMap
shiftRL :: Word64 -> Int -> Word64
shiftRL (W64# x) (I# i) = W64# (shiftRL# x i)

Matt

comment:3 Changed 7 years ago by merehap

Cc: merehap@… added

comment:4 Changed 7 years ago by gwicke

Cc: gabriel@… added

I have created a package with bindings to GCC's built-in bit operations, which normally exploit native instructions and are thus faster than an implementation in terms of current Data.Bits primitives:

This fills my current needs, but is just a stop-gap until GHC has full support for these operations. Ticket #4102 discusses native support for these higher-level operations in GHC.

comment:5 Changed 7 years ago by igloo

Resolution: wontfix
Status: newclosed

This looks like an abandoned proposal. If that's not the case, please re-open and give a discussion summary and consensus decision, as described on the process page.

Note: See TracTickets for help on using tickets.