Il est très facile de comparer des doubles positifs: la normalisation nous garantit que des nombres avec des exposants différents, plus celui dont l'exposant est le plus grand est grand, et des nombres avec le même exposant, plus celui dont la mantisse est la plus grande est grand. La norme IEEE 754 a soigneusement placé l'exposant dans les bits de poids fort, de sorte que les doubles positifs peuvent être comparés simplement comme int64_t.
Les nombres négatifs sont un peu plus compliqués: ils sont stockés en code direct , tandis que int64_t est stocké en code complémentaire . Cela signifie que pour utiliser une comparaison d'entiers, les 63 bits inférieurs d'un double doivent être inversés (cela se traduira par -0. <+0., Ce qui ne correspond pas à la norme, mais en pratique ne présente pas de problème ). La vérification explicite des bits d'ordre élevé et le branchement conditionnel détruiraient tous les avantages de passer à la comparaison d'entiers; mais il existe un moyen plus simple!
inline int64_t to_int64(double x) {
int64_t a = *(int64_t*)&x;
uint64_t mask = (uint64_t)(a >> 63) >> 1;
return a ^ mask;
}
inline bool is_smaller(double x1, double x2) {
return to_int64(x1) < to_int64(x2);
}
a>>63
remplit les 64 bits avec des copies du bit de signe, puis
>>1
efface le bit le plus significatif.
Le blog de Daniel Lemire a un code légèrement différent (de la même complexité de calcul), mais ma version conserve la propriété utile que
to_int64(0.) == 0