Skip to main content
se añadieron 15 caracteres en el cuerpo
Origen Enlace
ChemaCortes
  • 8.9k
  • 22
  • 36

En Data.Bits existe una función, 'popCount, para contar el número de popCount1'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.

En Data.Bits existe una función, 'popCount, para contar el número de 1's` de un número:

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 tienes que hacerlo por tus 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 hecho parece ir bastante peor.

En Data.Bits existe una función, popCount, 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 hacer 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, incluso parece ir bastante peor.

Origen Enlace
ChemaCortes
  • 8.9k
  • 22
  • 36

En Data.Bits existe una función, 'popCount, para contar el número de 1's` de un número:

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 tienes que hacerlo por tus 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 hecho parece ir bastante peor.