En Yüksek Bit'i Bulma (Bit Scan Reverse)

Son güncelleme 6 Ağustos 2006 Pazar

Bir sayıdaki en yüksek basamaklı bit'den başlayarak ilk 1 değerli bit'i bulmak için x86 assembly'de BSR (Bit Scan Reverse) isimli bir komut vardır. C#'da ya da MSIL'de buna karşılık gelen bir komut malesef yok ama Visual C++ 8'de (VS.Net 2005) intrin.h'ı include ettiğinizde _BitScanReverse adıyla aynı işi gören bir fonksiyon geliyor.

Bu fonksiyonu hazırlarken de 4 farklı varyasyon çıktı. Hangisinin daha iyi olduğunu test ederek hızlı olanı seçtik ve sonucu sizlerle paylaşıyoruz.

Fonksiyonlardan dördü de aynı işi yapıyor, 64-bit unsigned integer (C#'da ulong, vb.net'de ise malesef işaretsiz tamsayılar framework 2.0'a kadar yok) bir sayıdan en yüksek set bit nosunu integer olarak döndürüyor, sayı 0 ise -1 dönüyor. Bu arada logaritma kullanan son fonksiyon sayı büyüdükçe doğru sonuç vermekten uzaklaşıyor.

Konuya uzak arkadaşlar için en yüksek bit'den neleri ifade etmek istediğimizi açarsak;

bit no :     7 6 5 4 3 2 1 0
             - - - - - - - - 
örnek sayı : 0 0 1 0 0 1 1 0    (38)
                 |
                 |__ soldan ilk 1 bit, basamak nosu 5

Yukarıdaki örnekte de görüldüğü gibi EnYuksekBit(38) fonksiyonu çağırıldığında 5 döner (sayı 0 olsaydı sonuç -1 dönerdi).

Aşağıda yer alan kod, 4 fonksiyondan en optimize olanı

// x86 BSR'nin yaptığı iş, soldan ilk bir biti bulur, 64-bit, sayı 0 ise -1 döner public static int EnYuksekBit(ulong sayi){ // Programlama: Serdar IRMAK (C)2005 http://www.argelab.net return sayi == 0 ? -1 : (((sayi > 0x00000000ffffffff) ? 32 : 0) + (((sayi & 0xffff0000ffff0000) > (sayi & 0x0000ffff0000ffff)) ? 16 : 0) + (((sayi & 0xff00ff00ff00ff00) > (sayi & 0x00ff00ff00ff00ff)) ? 8 : 0) + (((sayi & 0xf0f0f0f0f0f0f0f0) > (sayi & 0x0f0f0f0f0f0f0f0f)) ? 4 : 0) + (((sayi & 0xcccccccccccccccc) > (sayi & 0x3333333333333333)) ? 2 : 0) + (((sayi & 0xaaaaaaaaaaaaaaaa) > (sayi & 0x5555555555555555)) ? 1 : 0)); }

EnYuksekBit fonksiyonunun kullanım alanına örnek olarak byte uzunluk verildiğinde veri boyutunu birimli olarak döndüren bir fonksiyon yazabiliriz. Mesela 1937495 verdiğinizde 1,85 MB döndürecek:

public static string VeriUzunlugu(ulong byteUzunluk) { // Programlama: Serdar IRMAK (C)2005 http://www.argelab.net int i = (int)Math.Floor(EnYuksekBit((ulong)byteUzunluk) / 10); return (byteUzunluk / Math.Pow(1024, i)).ToString("0.## ") + "ByteKB MB GB TB PB ".Substring( i << 2, 4).Trim(); }

Hazır yeri gelmişken bit test etme, bit silme ve bit set etme fonksiyonlarını da verelim:

// Verilen değerin istenilen bitinin 1 olup olmadığını test eder public static bool BTST(ulong deger, int bit) { return (deger & (1UL << (bit & 0x3f))) != 0UL; } // Verilen değerin istenilen bitini 1 yapar public static ulong BSET(ulong deger, int bit) { return (deger | (1UL << (bit & 0x3f))); } // Verilen değerin istenilen bitini 0 yapar public static ulong BCLR(ulong deger, int bit) { return (deger & (~(1UL << (bit & 0x3f)))); }

 argelab_en_yuksek_bit.zip (79K)

ArgeLab.net, bu sitenin eksiksiz ve hatasız olduğu
konusunda bir garanti veremez. Bu sitede yer alan bilgilerin ve
programların kullanımı sonucu oluşabilecek zararlardan
sorumlu tutulamaz.