Soient et deux entiers ayant le même nombre de bits

La démonstration. $2^{p-1}\le a<2^p$ et $2^{p-1}\le b<2^p$ donnent

$$2^p=2^{p-1}+2^{p-1}\le a+b<2^p+2^p=2^{p+1},$$

c'est-à-dire exactement la définition de « $a+b$ s'écrit sur $p+1$ bits ». La borne $\max (p,q)+1$ du cours n'est donc pas seulement atteinte ici : elle est toujours atteinte quand les deux opérandes ont la même taille.

La vérification :

for p in range(1, 9):
    tailles = set()
    for x in range(2**(p - 1), 2**p):
        for y in range(2**(p - 1), 2**p):
            tailles.add(nb_bits(x + y))
    assert tailles == {p + 1}

Le contraste. Si $a$ a $6$ bits et $b$ seulement $5$, la somme peut rester sur $6$ bits : $32+31=63$ s'écrit sur $6$ bits, alors que $32+32=64$ en demande $7$.

Contrôle : $63=111111_2$ (six bits), $64=1000000_2$ (sept bits).