Calculer la moyenne de 2 `unsigned int` sans overflow
(devblogs.microsoft.com)- Les additionner puis diviser par 2 provoque un overflow
→ (a + b) / 2
- Si l’on connaît le plus grand des deux nombres, on peut aussi ajouter à la plus petite valeur la moitié de l’écart entre les deux
→ low + (high - low) / 2
- Un algorithme qui fonctionne même sans savoir lequel est le plus grand est tombé dans le domaine public après l’expiration du brevet en 2016
→ (a / 2) + (b / 2) + (a & b & 1)
- SWAR : SIMD within a register
→ (a & b) + (a ^ b) / 2
- Si le compilateur prend en charge le 64 bits, on peut faire un cast
→ ((unsigned long long)a + b) / 2
- Et ensuite viennent des morceaux de code assembleur selon les processeurs… reportez-vous à l’article original
1 commentaires
Le blog de Raymond Chen, The Old New Thing, couvre des sujets variés, des coulisses du développement de Windows à bien d’autres thèmes.
En Corée, une traduction intitulée « Les 282 histoires du développement de Windows par Raymond Chen » a été publiée, mais elle est aujourd’hui épuisée.