Aujourd'hui, test surprise de C. Tout le monde s'assied, pas de discussion et fermez la porte svp. Voilà les copies, silence et vous avez dix minutes pour répondre.
Da test
/* return the absolute value of the given argument x. */ int abs(int x) { if (x < 0) return (-x); else return (x); }
Est ce que cette fonction renvoie toujours la bonne valeur?
Absolument!
J'espère que vous avez répondu oui. Sinon je post pour rien :)
Absolument pas!
En faite non. Cette fonction a un "bug", comme la vaste majorité des fonctions abs() que l'on rencontre dans la vraie vie (ça veut dire "pas dans un cours d'algo").
Pour comprendre le "bug", il faut comprendre comment sont représentés les nombres dans notre machine. Toutes les informations gérées par la machine sont en binaire, plus précisément pour un nombre entier c'est en base deux.
Retour à l'école, la base 2
On compte généralement en base dix dans notre civilisation (historiquement, certaines civilisations avaient d'autres bases). Si on avait deux doigts (un à chaque main) on compterait certainement en base deux, et je pondrais ce post avec beaucoup plus de difficulté (le lecteur astucieux notera ici que ce post n'aurait aucun intérêt dans le cas sus cité). La base dix, ça veut dire qu'on représente notre nombre comme une addition de puissances de dix. Par exemple, mille trois cent trente-sept s'écrit 1337:
(1 * 10^3) + (3 * 10^2) + (3 * 10^1) + (7 * 10^0)
En base deux, zéro s'écrit 0, un s'écrit 1 et deux s'écrit 10 (d'où la vieille blague: "Il n'y a que 10 type de personnes: ceux qui savent compter en base deux et les autres). Si on généralise l'idée de la décomposition qu'on a faite en base dix pour 1337, en base deux on représente quarante-deux par 101010:
(1 * 2^5) + (0 * 2^4) + (1 * 2^3) + (0 * 2^2) + (1 * 2^1) + (0 * 2^0)
Allez on continue sur la lancée
Tu ne vois pas où je veux en venir, mais c'est pas grave ("hééé, c'est comme à l'école!" j'entends au fond). Maintenant les additions! On va additionner 1337 et 42:
1337
+ 42
-----
1379
Et maintenant en base deux. yarly™.
1337 -> 10100111001
+ 42 -> + 101010
----- ------------
1379 10101100011
Si on fait le petit calcul, on voit bien que 1379 en base deux c'est 10101100011.
Ok facile, mais les nombres négatifs?
À partir de maintenant on va représenter nos nombres entiers sur 8 bits.
La première idée serait de mettre un bit pour le signe (le plus fort), 0 si le nombre est positif et 1 si le nombre est négatif, ainsi on représenterait 42 avec 00101010 et -42 avec 10101010. Cette représentation pose deux problèmes, le premier c'est qu'il y a maintenant deux façon différente d'écrire zéro (00000000 et 10000000), et la deuxième c'est qu'on ne peut plus additionner, par exemple (11 + (-3)):
11 -> *0*0001011
+ -3 -> + *1*0000011
----- ------------
8 *1*0001110
Le résultat est -14 !
Complément à deux
Dans notre machine, les nombre entiers sont représenté en complément à deux. Pour les nombres entiers positifs, ça ne change rien, mais pour les négatifs la représentation est différente que ci dessus. Pour trouver la représentation d'un entier négatif en complément à deux il faut procéder de cette manière:
- On prend sa version positive
- On inverse tous les bit (tout ceux à 0 passent à 1, et réciproquement)
- On ajoute 1 (en ignorant les dépassements)
Par exemple, pour transformer 6 en -6:
- 00000110
- 11111001
- 11111010
L'avantage de cette représentation élimine nos deux problèmes:
- vu que suivant cet algorithme, 00000000 devient 00000000, on a bien une seule représentation de zéro.
- on peut additionner un nombre négatif et positif facilement:
42 -> *0*0101010
+ -6 -> +*1*1111010
----- ------------
36 *0*0100100
Maintenant si on prend 01010100 ont voit bien que c'est 36 en représentation binaire! La magie du complément à deux fait que si on applique la transformation ci-dessus à un nombre négatif, on trouve sa valeur positive.
Le problème
L'inconvénient de cette méthode, c'est que par exemple sur 8 bits on peut représenter les nombres de -128 à +127, voici une jolie image piquée à Wikipédia:
Donc, si on respecte la représentation, il n'est pas possible de faire une fonction abs() correcte, vu qu'il n'y a pas de moyen de représenter la plus petite valeur (-128 sur 8 bits) de manière positive! Il faudrait changer de représentation (par exemple, retourner une valeur sur 16 bits), ce qui n'est vraiment pas pratique. On voit que le nombre négatif le plus "petit" (ou si vous préférez, "le plus négatif") est représenté par un 1 et tout le reste de zéro, si on applique la transformation du complément à deux sur -128:
- 10000000
- 01111111
- 10000000
On est retombé sur -128 !
et donc, abs() dans tout ça?
Donc abs() renvoie x s'il est positif, ou son complément à deux si il est négatif. On a vu que pour zéro son complément à deux et lui même sont représentés de la même façon, ainsi que que pour le nombre négatif le plus "petit" (-128 dans notre exemple sur 8 bits).
Dans le manuel de la plus part des langages on trouve quelque chose comme ça:
BUGS
The absolute value of the most negative integer remains negative.
C'est valable pour tous les langages qui ne font pas de changement de représentation automatique lors d'overflow, c'est à dire C, C++, Java ...
Les langages plus dynamiques comme Python ou Ruby détectent l'overflow, et changent la représentation automatiquement (pour Python par exemple, on passe de int à long). Voici l'exemple en Python:
>>> minimum = -sys.maxint - 1 >>> type(minimum) <type 'int'> >>> type(-minimum) <type 'long'>
