Números binarios invertidos

PorJosé A. Alonso 6-marzo-201713-marzo-2017

La representación binaria de 13 es 1101, que al invertirlo da 1011 cuya representación decimal es el número 11.

Definir la función

   transformado :: Integer -> Integer

1	transformado :: Integer -> Integer

tal que (transformado x) es la representación decimal del número obtenido invirtiendo la representación binaria de x. Por ejemplo,

   transformado 13  ==  11
   transformado 47  ==  61

1 2	transformado 13 == 11 transformado 47 == 61

Nota: El ejercicio está basado en el problema Reversed Binary Numbers de Kattis.

Soluciones

transformado :: Integer -> Integer 
transformado = bin2int . reverse . int2bin

-- (int2bin x) es la representación binaria de x. Por ejemplo,
--    int2bin 13  ==  [1,0,1,1]
int2bin :: Integer -> [Integer]
int2bin n | n < 2     = [n]
          | otherwise = n `mod` 2 : int2bin (n `div` 2)

-- (bin2int x) es la representación decimal del número binario x. Por
-- ejemplo, 
--    bin2int [1,0,1,1]           ==  13
--    bin2int (reverse [1,0,1,1]) ==  11
bin2int :: [Integer] -> Integer
bin2int =  foldr (\x y -> x + 2*y) 0

transformado :: Integer -> Integer

transformado = bin2int . reverse . int2bin

-- (int2bin x) es la representación binaria de x. Por ejemplo,

-- int2bin 13 == [1,0,1,1]

int2bin :: Integer -> [Integer]

int2bin n | n < 2 = [n]

| otherwise = n `mod` 2 : int2bin (n `div` 2)

-- (bin2int x) es la representación decimal del número binario x. Por

-- ejemplo,

-- bin2int [1,0,1,1] == 13

-- bin2int (reverse [1,0,1,1]) == 11

bin2int :: [Integer] -> Integer

bin2int = foldr (\x y -> x + 2*y) 0

10 Comentarios

bin2int :: [Integer] -> Integer
bin2int = foldr (\x y -> x + 2*y) 0

int2bin :: Integer -> [Integer]
int2bin n | n<2 = [n]
          | otherwise = n `mod` 2 : int2bin (n `div` 2)

transformado :: Integer -> Integer
transformado = f.bin2int.reverse.int2bin.f
             where f = fromIntegral

bin2int :: [Integer] -> Integer

bin2int = foldr (\x y -> x + 2*y) 0

int2bin :: Integer -> [Integer]

int2bin n | n<2 = [n]

| otherwise = n `mod` 2 : int2bin (n `div` 2)

transformado :: Integer -> Integer

transformado = f.bin2int.reverse.int2bin.f

where f = fromIntegral

Responder

transformado :: Integer -> Integer
transformado  = foldl' (\x y -> 2*x + y) 0 . aBinario2
              where
               aBinario2 0 = [0]
               aBinario2 1 = [1]
               aBinario2 n = n `mod` 2 : aBinario (n `div` 2)

transformado :: Integer -> Integer

transformado = foldl' (\x y -> 2*x + y) 0 . aBinario2

where

aBinario2 0 = [0]

aBinario2 1 = [1]

aBinario2 n = n `mod` 2 : aBinario (n `div` 2)

Responder

transformado x = aux p (length p - 1)
       where p = int2bin x
             int2bin 0 = []
             int2bin x = (rem x 2):int2bin (div x 2)
             aux [] _ = 0
             aux (x:xs) p = x*(2^p) + aux xs (p-1)

transformado x = aux p (length p - 1)

where p = int2bin x

int2bin 0 = []

int2bin x = (rem x 2):int2bin (div x 2)

aux [] _ = 0

aux (x:xs) p = x*(2^p) + aux xs (p-1)

Responder

import Numeric (showIntAtBase)
import Data.Char (intToDigit, digitToInt)
import Control.Arrow
import Data.Bits
import Test.QuickCheck hiding ((.&.))
import System.Environment

-- a cadena y desde cadena
transformado :: Integer ->Integer
transformado = sum . zipWith (*) ((2^) <$> [0..])
                      . map  (toInteger     . digitToInt)
                      . flip (showIntAtBase 2 intToDigit) ""


-- dividiendo
transformado' :: Integer ->Integer
transformado' = fst . t
  where t 0 = (0, 1)
        t n = let ((s, p), r) = first t $ n `divMod` 2
              in  (s + r * p, 2 * p)


-- desplazando bits
transformado'' :: Integer ->Integer
transformado'' = t 0
  where t r 0 = r
        t r a = t (r `shiftL` 1 .|. a .&. 1) (a `shiftR` 1)


-- diferente implementación, igual resultado
test n = let x = abs n
             r = transformado   x
             s = transformado'  x
             t = transformado'' x
         in  r == s && r == t

{-

> quickCheckWith (stdArgs { maxSuccess = 1000000 }) test
+++ OK, passed 1000000 tests.

-- sin compilar ==============================
> :set +s
> sum $ map transformado [1..1000000]
341034378052
(6.82 secs, 9,809,436,680 bytes)
> sum $ map transformado' [1..1000000]
341034378052
(66.24 secs, 22,993,089,632 bytes)
> sum $ map transformado'' [1..1000000]
341034378052
(34.79 secs, 12,421,041,832 bytes)


-- compilado ===============================
[josejuan@centella centella]$ for i in 0 1 2; do time -f "%E, %M" ../bininv $i 2000000; done
1364140870916
0:06.48, 3860
1364140870916
0:05.19, 3952
1364140870916
0:04.20, 3960


--}

main = do
  [t, c] <-map read <$> getArgs
  let f = case t of
            0 ->transformado
            1 ->transformado'
            2 ->transformado''
  print $ sum $ map f [1..c]

import Numeric (showIntAtBase)

import Data.Char (intToDigit, digitToInt)

import Control.Arrow

import Data.Bits

import Test.QuickCheck hiding ((.&.))

import System.Environment

-- a cadena y desde cadena

transformado :: Integer ->Integer

transformado = sum . zipWith (*) ((2^) <$> [0..])

. map (toInteger . digitToInt)

. flip (showIntAtBase 2 intToDigit) ""

-- dividiendo

transformado' :: Integer ->Integer

transformado' = fst . t

where t 0 = (0, 1)

t n = let ((s, p), r) = first t $ n `divMod` 2

in (s + r * p, 2 * p)

-- desplazando bits

transformado'' :: Integer ->Integer

transformado'' = t 0

where t r 0 = r

t r a = t (r `shiftL` 1 .|. a .&. 1) (a `shiftR` 1)

-- diferente implementación, igual resultado

test n = let x = abs n

r = transformado x

s = transformado' x

t = transformado'' x

in r == s && r == t

> quickCheckWith (stdArgs { maxSuccess = 1000000 }) test

+++ OK, passed 1000000 tests.

-- sin compilar ==============================

> :set +s

> sum $ map transformado [1..1000000]

341034378052

(6.82 secs, 9,809,436,680 bytes)

> sum $ map transformado' [1..1000000]

341034378052

(66.24 secs, 22,993,089,632 bytes)

> sum $ map transformado'' [1..1000000]

341034378052

(34.79 secs, 12,421,041,832 bytes)

-- compilado ===============================

[josejuan@centella centella]$ for i in 0 1 2; do time -f "%E, %M" ../bininv $i 2000000; done

1364140870916

0:06.48, 3860

1364140870916

0:05.19, 3952

1364140870916

0:04.20, 3960

--}

main = do

[t, c] <-map read <$> getArgs

let f = case t of

0 ->transformado

1 ->transformado'

2 ->transformado''

print $ sum $ map f [1..c]

Responder

transformado :: Integer -> Integer
transformado x = sum (zipWith (*) (reverse xs) ys)
  where xs = binarioDecimal x
        ys = [2^n | n <- [0..]]
        
binarioDecimal 0 = []
binarioDecimal x =rem x 2 : binarioDecimal (div x 2)

transformado :: Integer -> Integer

transformado x = sum (zipWith (*) (reverse xs) ys)

where xs = binarioDecimal x

ys = [2^n | n <- [0..]]

binarioDecimal 0 = []

binarioDecimal x =rem x 2 : binarioDecimal (div x 2)

Responder

transformado :: Integer -> Integer
transformado  = reprDec . reverse . binario

binario  :: Integer -> [Integer]
binario n | n < 2     = [n]
          | otherwise = n `mod` 2 : binario (n `div` 2)

reprDec :: [Integer] -> Integer
reprDec =  foldr (\x y -> x + 2*y) 0

transformado :: Integer -> Integer

transformado = reprDec . reverse . binario

binario :: Integer -> [Integer]

binario n | n < 2 = [n]

| otherwise = n `mod` 2 : binario (n `div` 2)

reprDec :: [Integer] -> Integer

reprDec = foldr (\x y -> x + 2*y) 0

Responder

transformado :: Integer -> Integer
transformado x = head(reverse (aux 2 0 (binario x)))
    where aux _ _ [] = []
          aux n d (x:xs) = (n*d + x) : aux n (n*d+x) xs

binario :: Integral t => t -> [t]
binario x | x < 2 = [x]
          | otherwise = x `mod` 2 : binario (x `div`2)

transformado :: Integer -> Integer

transformado x = head(reverse (aux 2 0 (binario x)))

where aux _ _ [] = []

aux n d (x:xs) = (n*d + x) : aux n (n*d+x) xs

binario :: Integral t => t -> [t]

binario x | x < 2 = [x]

| otherwise = x `mod` 2 : binario (x `div`2)

Responder

transformado :: Integer -> Integer

transformado x  = bin2int ( reverse (int2bin x))

bin2int = foldr (\ x y -> x + 2*y) 0

int2bin n | n < 2 = [n]
          | otherwise = n `mod` 2 : int2bin (n`div` 2)

transformado :: Integer -> Integer

transformado x = bin2int ( reverse (int2bin x))

bin2int = foldr (\ x y -> x + 2*y) 0

int2bin n | n < 2 = [n]

| otherwise = n `mod` 2 : int2bin (n`div` 2)

Responder

decimalBinarioInv :: Integer -> [Int]
decimalBinarioInv 0 = []
decimalBinarioInv n = ((mod (fromIntegral n) 2):(decimalBinarioInv (div  n 2)))

binarioDecimal :: [Int] -> Integer
binarioDecimal [] = 0
binarioDecimal (x:xs) = (fromIntegral x)*(2^(length xs)) + binarioDecimal xs

transformado :: Integer -> Integer
transformado n = binarioDecimal (decimalBinarioInv n)

decimalBinarioInv :: Integer -> [Int]

decimalBinarioInv 0 = []

decimalBinarioInv n = ((mod (fromIntegral n) 2):(decimalBinarioInv (div n 2)))

binarioDecimal :: [Int] -> Integer

binarioDecimal [] = 0

binarioDecimal (x:xs) = (fromIntegral x)*(2^(length xs)) + binarioDecimal xs

transformado :: Integer -> Integer

transformado n = binarioDecimal (decimalBinarioInv n)

Responder

transformado :: Integer -> Integer
transformado = deBase2 . enBase2

enBase2 :: Integer -> [Integer]
enBase2 x | x < 2     = [x]
          | otherwise = x `mod` 2 : enBase2 (x `div` 2)

deBase2 :: [Integer] -> Integer
deBase2 xs = aux 0 (reverse xs)
       where aux _ []     = 0
             aux n (x:xs) = 2^n * x + aux (n+1) xs

transformado :: Integer -> Integer

transformado = deBase2 . enBase2

enBase2 :: Integer -> [Integer]

enBase2 x | x < 2 = [x]

| otherwise = x `mod` 2 : enBase2 (x `div` 2)

deBase2 :: [Integer] -> Integer

deBase2 xs = aux 0 (reverse xs)

where aux _ [] = 0

aux n (x:xs) = 2^n * x + aux (n+1) xs

Responder

Números binarios invertidos

Soluciones

10 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

10 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico