Htirage/Bits.hs

   1 -- | Manipulation de bits.
   2 module Htirage.Bits where
   3
   4 import Data.Bits
   5 import Data.List
   6
   7 import Htirage.Combinatorics
   8
   9 -- | @nbBits n@ retourne le nombre de bits servant à encoder 'n'.
  10 nbBits :: FiniteBits i => i -> Int
  11 nbBits n = finiteBitSize n - countLeadingZeros n
  12
  13 -- | @intOfBits bs@ retourne le nombre encodé par les bits 'bs'.
  14 intOfBits :: (FiniteBits i, Num i) => [Bool] -> i
  15 intOfBits bs = foldr (.|.) 0 (zipWith (\i b -> if b then bit i else 0) [0..] bs)
  16
  17 -- | @bitsOfInt m n@ retourne les 'm' premiers bits de poids faible encodant le nombre 'n'.
  18 bitsOfInt :: FiniteBits i => Int -> i -> [Bool]
  19 bitsOfInt m n = [testBit n i | i <- [0..m-1]]
  20
  21 -- | @equiprobableBits n@ retourne l’exposant
  22 -- de la plus grande puissance de 2 inférieure ou égale 'n'.
  23 equiprobableBits :: (FiniteBits i, Num i) => i -> Int
  24 equiprobableBits n | n == 2 ^ b = b
  25                    | otherwise  = b - 1
  26                    where b = nbBits n
  27
  28 -- | @bitsOfComb n k c@ retourne des bits équiprobables donnés
  29 -- par la combinaison 'c' obtenue par tirage équiprobable
  30 -- d’une combinaison de 'k' entiers parmi @[1..n]@.
  31 --
  32 -- Pour que les bits retournés aient chacun
  33 -- la même probabilité d’être à 'True' ou à 'False',
  34 -- seulement les combinaisons de rang lexicographique inférieur ou égal
  35 -- à la plus grande puissance de 2 inférieure ou égal à @k`combsIn`n@
  36 -- sont considérées comme valides ; les autres donnant des doublons.
  37 --
  38 -- Dans le cas où survient une combinaison invalide,
  39 -- aucun bit n’est extrait du tirage 'c'.
  40 bitsOfComb :: (FiniteBits i, Integral i) => i -> i -> [i] -> [Bool]
  41 bitsOfComb n k c =
  42         case rankOfComb n (sort c) of
  43          r | nbBits r <= epBits -> epBits `bitsOfInt` r
  44          _ -> []
  45         where epBits = equiprobableBits (n`nCk`k)