Htirage/Bits.hs

   1 -- | Manipulation de bits.
   2 module Htirage.Bits where
   3
   4 -- | @nbBits n@ retourne le nombre de bits servant à encoder 'n'.
   5 nbBits :: Integer -> Int
   6 nbBits n | 0<=n      = go n
   7          | otherwise = undefined
   8          where go 0 = 0
   9                go i = 1 + go (i`div`2)
  10
  11 -- | @integerOfBits bs@ retourne le nombre encodé par les bits 'bs'.
  12 integerOfBits :: [Bool] -> Integer
  13 integerOfBits []     = 0
  14 integerOfBits (b:bs) = integerOfBits bs * 2 + (if b then 1 else 0)
  15
  16 -- | @bitsOfInteger m n@ retourne les 'm' premiers bits de poids faible
  17 -- encodant le nombre 'n'.
  18 bitsOfInteger :: Int -> Integer -> [Bool]
  19 bitsOfInteger m n | 0<=m,0<=n = go m n
  20                   | otherwise = undefined
  21                   where go 0 _ = []
  22                         go i j = (r==1) : go (i-1) q
  23                                where (q,r) = j`divMod`2
  24
  25 -- | @randomIntOfBits n bs@ retourne le premier entier 'i' formé par les bits 'bs'
  26 -- qui a le potentiel d’atteindre un entier dans @[0..n-1]@,
  27 -- ou recommence en ignorant le premier bit si @n < i@.
  28 randomIntegerOfBits :: Integer -> [Bool] -> Integer
  29 randomIntegerOfBits n bs | given < enough = error (show (enough - given) ++ " bits missing")
  30                          | n < i          = randomIntegerOfBits n (tail bits ++ bs')
  31                          | otherwise      = i
  32         where (bits, bs') = splitAt enough bs
  33               i           = integerOfBits bits
  34               given       = length bits
  35               enough      = nbBits n