0

Buenas tardes.

¿Hay alguna función que permita pasar de decimal a binario? Por ejemplo,

toBin 12 = [1,1,0,0]

toBin 2^38-174 = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,0,0,1,0]

toBin 1215484521248 = [1,0,0,0,1,1,0,1,1,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,1,1,1,1,0,1,0,1,1,0,0,1,0,0,0,0,0]

He intentado hacerlo mediante recursión, de la siguiente forma, pero es muy poco eficiente, pues en los ejemplos anteriores, ni me lo da en el mismo orden y tarda mucho.

toBin 0 = [0]

toBin n | mod n 2 == 1 = toBin (div n 2) ++ [1]

        | mod n 2 == 0 = toBin (div n 2) ++ [0]

Asimismo, después necesito que me diga el número de unos que hay en el número Por ejemplo,

numeroUnos [1,1,0,0] = 2

Este último no se me ha ocurrido nada para hacerlo.

ACTUALIZADO.2

El problema es que me lo piden para este número 20^100000000+37, y ambas definciones son ineficientes, tanto la mía como la de los comentario.

numeroUnos (1+10^20000000) = a

Necesito la función que me diga cuantos unos tiene ese numero en binario, en menos, de 10 segundos.

Muchas gracias y un saludo.

1
  • @ChemaCortes a ver si me puedes ayudar, porque eres un genio en Haskell. Además, creo que eres de los pocos aquí que lo entiendes.
    – Carlos
    Commented el 13 ene. 2018 a las 19:41

3 respuestas 3

1

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.

1

Decimal a binario

El problema de tu implementación es que estás concatenando cada dígito al final de la lista en cada iteración. El operador ++ tiene un coste lineal respecto al número de elementos de la primera lista. Por lo tanto, si el número binario tiene n dígitos, hace (n-1) + (n-2) + (n-3) + ... + (n-n) = 1 + 2 + 3 + ... + (n-1) iteraciones para construir la lista final, cuya progresión es igual a (n-1)*n/2, resultando un orden de complejidad cuadrático respecto al número de dígitos del número binario.

Lo más común es construir la lista al revés (encabezando los elementos con :), y darle la vuelta al final con reverse en una única pasada. El operador : es el constructor de listas, que toma un elemento x y una lista xs y devuelve (en tiempo constante) la lista x:xs con cabeza x y cola xs. La función reverse invierte una lista en tiempo lineal, por lo tanto la función resultante tiene un orden de complejidad lineal respecto al número de dígitos del número binario:

toBin, auxBin :: Int -> [Int]
toBin 0 = [0]
toBin n = reverse (auxBin n)

auxBin 0 = []
auxBin n = n `mod` 2 : auxBin (n `div` 2)

Número de unos

Para contar el número de 1 de la lista resultante, puedes filtrar los elementos iguales a 1 con la función filter, y luego calcular la longitud con la función length:

ghci> filter (==1) [1,0,0,1,1]
[1,1,1]
ghci> length (filter (==1) [1,0,0,1,1])
3

Combinándolo con toBin en una función:

countOnes :: Int -> Int
countOnes = length . (filter (==1)) . toBin

Otra opción más simple, utilizando simplemente ajuste de patrones:

numeroUnos :: [Int] -> Int
numeroUnos [] = 0
numeroUnos (1:xs) = 1 + numeroUnos xs
numeroUnos (_:xs) = numeroUnos xs
1
  • Muchas gracias. Pero, sigue siendo poco eficiente para el ejercicio que me proponen que es calcular el numero de unos (en binario) de 2^100000000.
    – Carlos
    Commented el 14 ene. 2018 a las 8:19
1

Para calcular el número de unos, population count, no es necesario convertir el número a binario; puedes, por ejemplo, hacer uso del hecho de que x & (x - 1) tiene un uno menos que x,

import Data.Bits

population_do 0 p = p
population_do x p = population_do ((.&.) x (x - 1)) (p + 1)
population x = population_do x 0
2
  • Me funciona muy bien, pero no la entiendo
    – Carlos
    Commented el 14 ene. 2018 a las 18:41
  • Gracias, pero para el caso que me ponen no es eficiente numeroUnos (1+10^20000000)
    – Carlos
    Commented el 14 ene. 2018 a las 19:09

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.