Perbandingan ganda yang cepat

Kemarin ada artikel tentang fast parsing ganda, saya pergi ke blog penulisnya, dan menemukan trik menarik lainnya disana . Saat membandingkan angka floating point, perhatian khusus harus diberikan pada NaN (delapan tahun yang lalu saya menulis tentang mereka secara lebih rinci); tetapi jika angka yang dibandingkan tentu bukan NaN, maka mereka dapat dibandingkan lebih cepat dari prosesor!



Sangat mudah untuk membandingkan ganda positif: normalisasi menjamin kita bahwa dari bilangan dengan eksponen berbeda, semakin besar bilangan yang eksponennya lebih besar, dan dari bilangan dengan eksponen yang sama, semakin besar bilangan yang mantisanya lebih besar. Standar IEEE 754 telah menempatkan eksponen dengan hati-hati dalam bit orde tinggi, sehingga ganda positif dapat dibandingkan hanya sebagai int64_t.







Bilangan negatif sedikit lebih rumit: disimpan dalam kode langsung , sedangkan int64_t disimpan dalam kode pelengkap . Ini berarti bahwa untuk menggunakan perbandingan bilangan bulat, 63 bit ganda yang lebih rendah harus dibalik (ini akan menghasilkan -0. <+0., Yang tidak sesuai dengan standar, tetapi dalam praktiknya tidak menimbulkan masalah ). Pemeriksaan bit orde tinggi yang eksplisit dan percabangan bersyarat akan menghancurkan semua manfaat dari melompat ke perbandingan integer; tapi ada cara yang lebih mudah!

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



mengisi semua 64 bit dengan salinan bit tanda, dan kemudian >>1



membersihkan bit yang paling signifikan.



Blog Daniel Lemire memiliki kode yang sedikit berbeda (dengan kompleksitas komputasi yang sama), tetapi versi saya mempertahankan properti berguna yang to_int64(0.) == 0