Ticket #2376: Popcount.hs

File Popcount.hs, 743 bytes (added by mjark, 6 years ago)

Two population count functions using shiftR and shift

Line 
1module Popcount where
2
3import Data.Bits
4import Data.Word
5
6popcount32shift :: Word32 -> Word32
7popcount32shift x0 = 
8        let x1 = (x0 .&. 0x55555555) + ((x0 `shift` (-1)) .&. 0x55555555) in
9        let x2 = (x1 .&. 0x33333333) + ((x1 `shift` (-2)) .&. 0x33333333) in
10        let x3 = x2 + (x2 `shift` (-4)) in
11        let x4 = (x3 .&. 0x000F000F) + ((x3 `shift` (-8)) .&. 0x000F000F) in
12        (x4 + (x4 `shift` (-16))) .&. 0x000000FF
13
14popcount32shiftR :: Word32 -> Word32
15popcount32shiftR x0 = 
16        let x1 = (x0 .&. 0x55555555) + ((x0 `shiftR` 1) .&. 0x55555555) in
17        let x2 = (x1 .&. 0x33333333) + ((x1 `shiftR` 2) .&. 0x33333333) in
18        let x3 = x2 + (x2 `shiftR` 4) in
19        let x4 = (x3 .&. 0x000F000F) + ((x3 `shiftR` 8) .&. 0x000F000F) in
20        (x4 + (x4 `shiftR` 16)) .&. 0x000000FF