Schneller Doppelvergleich

Gestern gab es einen Artikel über das schnelle Parsen von Doppel, ich ging zum Blog seines Autors und fand dort einen weiteren interessanten Trick . Wenn Gleitkommazahlen verglichen wird , hat ein besonderes Augenmerk auf NaN zu zahlen (vor acht Jahren ich schrieb über sie im Detail); Aber wenn die verglichenen Zahlen sicherlich nicht NaN sind, können sie schneller verglichen werden als der Prozessor!



Es ist sehr einfach, positive Doppelte zu vergleichen: Die Normalisierung garantiert uns, dass von Zahlen mit unterschiedlichen Exponenten je größer derjenige ist, dessen Exponent größer ist, und von Zahlen mit demselben Exponenten derjenige größer ist, dessen Mantisse größer ist. Der IEEE 754-Standard hat den Exponenten sorgfältig in die höherwertigen Bits eingefügt, sodass positive Doppelte einfach als int64_t verglichen werden können.







Negative Zahlen sind etwas komplizierter: Sie werden im direkten Code gespeichert , während int64_t im komplementären Code gespeichert wird . Dies bedeutet, dass zur Verwendung eines ganzzahligen Vergleichs die unteren 63 Bits eines Doppels invertiert werden müssen (dies führt zu -0. <+0., Was nicht dem Standard entspricht, aber in der Praxis kein Problem darstellt ). Eine explizite Bitprüfung höherer Ordnung und eine bedingte Verzweigung würden alle Vorteile eines Sprunges zum Ganzzahlvergleich zerstören. aber es gibt einen einfacheren Weg!

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



Füllt alle 64 Bits mit Kopien des Vorzeichenbits und >>1



löscht dann das höchstwertige Bit.



Daniel Lemires Blog hat etwas anderen Code (mit der gleichen Rechenkomplexität), aber meine Version behält die nützliche Eigenschaft bei to_int64(0.) == 0