Le masque qui déborde

Les deux cas sont des comportements indéfinis au sens de la norme C99 : décaler un int de $31$ rangs ou plus dépasse la largeur du type. La norme n'exige rien, et le compilateur ne signale rien. Il faut donc mesurer ce que produit la machine devant soi. Compilé avec gcc -Wall -Wextra -std=c99, aucun avertissement n'est émis, et l'exécution donne :

$n$	`(1 << n)`	tours de boucle
29	$536870912$	$536870912$
30	$1073741824$	$1073741824$
31	$- 2147483648$	0
32	$1$	1

Pour $n = 31$ , le bit de poids fort est le bit de signe : $1 ≪ 31$ vaut INT_MIN, la condition masque < (1 << n) est fausse d'emblée et la boucle ne s'exécute pas une seule fois. Pour $n = 32$ , le décalage a été fait modulo $32$ : $1 ≪ 32$ vaut $1$ , et la boucle ne visite que le sous-ensemble vide.

Le piège est complet : aucune erreur de compilation, aucune erreur d'exécution, aucun résultat — et un programme qui rend « aucune solution » sur les instances de taille $31$ alors qu'il en trouvait à $30$ . C'est le dépassement silencieux du chapitre chap:langage-c, à un endroit où on ne le cherche pas.

La parade : écrire la borne sur un type assez large, et documenter la limite.


/* Énumère les 2^n sous-ensembles. Précondition : 0 <= n <= 62. */
assert(0 <= n && n <= 62);
for (unsigned long long masque = 0; masque < (1ULL << n); masque = masque + 1) {
    /* ... */
}

Mesuré : 1ULL << 31 vaut $2147483648$ et 1ULL << 32 vaut $4294967296$ . Cela dit, à $n = 62$ la boucle ne finira jamais : la vraie limite reste celle de l'exercice précédent.

Énoncé

Corrigé

Exercices semblables