Continuons cette série sur les codes fantastiques avec un problème apparemment simple : calculer la moyenne de deux entiers.
Calculer une moyenne entre deux entiers, quoi de plus simple ? Je livre à vos yeux avides une implémentation en Python :
Époustouflant, n’est-ce pas ? Allez, sur notre lancée, la même chose en C :
Facile ! Décidément, le contenu de cette rubrique périclite. Testons cette fonction par acquit de conscience : average(5u, 3u) ? 4, OK. average(1234u, 5678u) ? 3456, OK. Allez, un dernier pour la route average(42424242u, 42424242u) ? 2094940594. 2094940594 ?!?
Maiscestbiensûr, 42424242u > (1u << 31), on a un beau dépassement de la capacité d’un entier sur 32 bits, taille d’un entier sur ma machine ! Comment faire ? Une solution naïve serait de faire le calcul sur un entier de taille supérieure, p. ex. (unsigned)(((long)x + y / 2), mais rien dans le standard ne nous garantit que cela existe.
On peut imaginer s’en sortir avec un peu de math :
Cela marche sur notre dernier exemple, mais échoue si x > y (on obtient 2147483650 pour average(4u, 0u)). On peut cependant ajouter une comparaison, un swap et le tour est joué :
Il existe cependant une solution bien plus amusante et sans branchement à base de manipulation de bits :
En effet, le ET logique nous dit, pour chaque bit, s’il y aura propagation de la retenue. Et si c’est le cas, le bit de retenue, qui devrait être déplacé à gauche, puis à droite à cause de la division par deux, est déjà positionné à la bonne place !
Le OU exclusif, quant à lui, effectue une addition bit à bit sans propagation de retenue. On le divise ensuite par deux et on ajoute la retenue, le compte est bon !
Un avantage de cette solution est qu’elle se calcule sans branchement, c’est donc une bonne candidate pour la vectorisation. C’est d’ailleurs la solution générique utilisée par la bibliothèque https://xsimd.readthedocs.io quand il n’existe pas de version matérielle pour cette opération (ce qui est le cas pour les entiers non signés de 8 et 16 bits en SSE, mais pas pour des entiers plus grands).
Et la version signée ? Vous semble-t-elle plus compliquée ?