CODEWITHSUNDEEP
haskell
Richard
Richard

Reputation: 487

Number of 1 bits in a decimal number

How can I write a function to return the number of 1 bits corresponding a decimal number? Maybe a square root function? The type should be this:

bits :: Int -> Int

EDIT: SOlved

uns :: Int -> Int
uns  0 = 0
uns 1 = 1
uns x | mod x 2 == 1 = 1 + uns (div x 2)
      | otherwise = uns (div x 2)

Upvotes: 2

Views: 916

Answers (4)

frasertweedale
frasertweedale

Reputation: 5674

Use popCount from Data.Bits, also known as the Hamming weight of a number. The advantage is that some CPUs have instructions specifically for calculating this, resulting in high performance.

λ> import Data.Bits
λ> :t popCount
popCount :: Bits a => a -> Int
λ> popCount 255
8
λ> popCount 0xa5
4

Upvotes: 5

ErikR
ErikR

Reputation: 52057

What about this old trick?

import Data.Bits

countOnes 0 = 0
countOnes x = 1 + countOnes (x .&. (x-1))

It only recurses n times where n is the number of one bits in x.

Of course, if you are going to import Data.Bits, then you might as well use popCount as @Cirdec suggested.

Upvotes: 7

Random Dev
Random Dev

Reputation: 52290

I guess Luka has the better version but maybe you struggle a bit with understanding it, so here is what I hinted at (which is the same Luka did only with naive recursion):

bits :: Int -> Int
bits 0 = 0
bits n = let (d,r) = n `divMod` 2
         in r + bits d

The idea is to get continous divide by 2 and look at the remainder - if it's 1 then you found a set bit, if not (it has to be 0 then) then there was none.

Upvotes: 3

Luka Rahne
Luka Rahne

Reputation: 10487

sum . map (`mod` 2) . takeWhile ( /= 0) . iterate (`quot` 2)

Upvotes: 4

Related Questions