Lire un entier en base 2

La définition

Soit (c₀, …, c_k) une famille de chiffres valant 0 ou 1, avec c_k ≠ 0. On note

   ‾c_k c_{k−1} … c₁ c₀‾ ²  =  somme des c_i · 2^i , pour i allant de 0 à k

On dit que (c₀, …, c_k) est la décomposition de n en base 2 lorsque n est égal à cette somme.

L'idée de la démonstration

Tout tient dans une observation : en isolant le terme d'indice 0,

   n = c₀ + 2·(c₁ + c₂·2 + … + c_k·2^{k−1})

Le facteur entre parenthèses est un entier, et c₀ vaut 0 ou 1. Or l'écriture n = 2q + r avec r dans {0, 1} est unique : c'est la division euclidienne par 2. Donc c₀ est forcément le reste de n par 2, et (c₁, …, c_k) est une décomposition du quotient.

De là découle tout le reste

Cette remarque transforme une question d'existence et d'unicité en une simple récurrence forte : le quotient est strictement plus petit que n, donc l'hypothèse de récurrence s'y applique. Le chiffre c₀ est imposé, les autres aussi par récurrence — d'où l'unicité, et l'existence par construction.

C'est aussi l'algorithme que tout le monde connaît : diviser par 2, noter le reste, recommencer, puis lire les restes à l'envers.

   41 = 2×20 + 1     reste 1
   20 = 2×10 + 0     reste 0
   10 = 2×5  + 0     reste 0
    5 = 2×2  + 1     reste 1
    2 = 2×1  + 0     reste 0
    1 = 2×0  + 1     reste 1

   41 s'écrit donc 101001 en base 2