En Data.Bits
existe una función, 'popCount, para contar el número de popCount
1's`, para contar el número de 1's
de un número en binario:
Prelude> import Data.Bits
Prelude> :set +s
Prelude Data.Bits> popCount (1+10^20000000)
23216588
(1.36 secs, 32,704,936 bytes)
Prelude Data.Bits> popCount (20^100000000+37)
116093520
(10.84 secs, 214,531,880 bytes)
Si lo tienes que hacerlohacer por tus propios medios, no conseguirás eficiencias mayores.
Sin usar Data.Bits
, se me ocurre algo así:
numeroUnos :: Integer -> Int
numeroUnos 0 = 0
numeroUnos n | odd n = numeroUnos (n `div` 2) + 1
| otherwise = numeroUnos (n `div` 2)
En lugar de ir bit por bit, podemos ir por bloques de 8 bits:
numeroUnos2 :: Integer -> Int
numeroUnos2 0 = 0
numeroUnos2 n = b256!!(fromInteger r) + numeroUnos2 d
where
b256 = [numeroUnos n | n <- [0..255]]
(d,r) = divMod n 256
Hay que notar que numeroUnos2
usa la función anterior, numeroUnos
, para calcular la lista b256
.
Podemos escalar e ir en bloques de 16 bits:
numeroUnos3 :: Integer -> Int
numeroUnos3 0 = 0
numeroUnos3 n = b16!!(fromInteger r) + numeroUnos3 d
where
b16 = [numeroUnos n | n <- [0..2^16-1]]
(d,r) = divMod n (2^16)
Pero no mejora mucho, de hechoincluso parece ir bastante peor.