← tüm yazılar
034

Brian Kernighan Algoritması

Geçen gün LeetCode’da 461. Hamming Distance sorusuna bakıyordum. İki tam sayı arasındaki farklı bitleri bulmam gerekiyordu. Çözümleri kurcalarken Brian Kernighan Algoritması denk geldi. Bit manipülasyonu (bit manipulation) tarafında bayağı popüler, temiz bir mantığı var. Bir sayının binary karşılığındaki “1” bitlerinin sayısını (yani PopCount veya Hamming Weight) en optimize şekilde bulmayı sağlıyor. Hoşuma gitti, buraya da not olarak düşmek istedim.

İlk Akla Gelen Geleneksel Yaklaşım

Soruyu ilk gördüğümde aklıma gelen ilk yöntem, herhalde çoğumuzun yapacağı gibi düz bir mantıktı: Sayıyı al, her adımda 1 bit sağa kaydır (>> 1) ve en sağdaki bitin 1 olup olmadığını anlamak için n & 1 kontrolü yap.

İş görüyor mu? Görüyor. Ama gereksiz bir ameleliği var. Bu yöntemle sayı ne olursa olsun (ister 1 olsun, ister 231-1), o veri tipinin tüm bitlerini tek tek kontrol etmek zorundayız. Yani elimizde 32-bit bir tam sayı varsa, döngü her senaryoda tam 32 kez dönüyor. Zaman karmaşıklığı (time complexity) de her zaman bit sayısı kadar, yani O(bit_sayısı) oluyor.

Brian Kernighan Mantığı Nedir?

Bu algoritmanın olayı, sayının içindeki tüm bitleri değil, sadece değeri “1” olan bitleri gezmesi. Yani sayının içinde sadece iki tane “1” biti varsa, sayı ne kadar büyük olursa olsun döngü sadece 2 kez çalışıyor. Boşu boşuna sıfırları saymakla uğraşmıyoruz.

Olay şu formülde bitiyor:

n & (n – 1)

Bir n sayısını kendisinin 1 eksiğiyle bit düzeyinde VE (&) işlemine soktuğumuzda, sayının en sağındaki “1” biti sıfıra (0) dönüşüyor.

Nasıl Çalışıyor?

Hemen n = 12 üzerinden denedim.

  • n = 12 → 1100 (Binary)
  • n – 1 = 11 → 1011 (Binary)

Bu ikisini & işlemine sokunca:

  1100  (12)
& 1011  (11)
-------
  1000  (8)  --> En sağdaki "1" biti sıfırlandı.

İlk adımda yeni sayımız n = 8 oldu. Döngünün sonraki adımında aynı işlemi tekrarlıyoruz:

  • n = 8 → 1000 (Binary)
  • n – 1 = 7 → 0111 (Binary)
  1000  (8)
& 0111  (7)
-------
  0000  (0)  --> Bir "1" daha silindi ve sayı 0 oldu, döngü bitti.

Toplamda sadece 2 adımda 12 sayısının içinde 2 tane “1” biti olduğunu bulduk. Geleneksel yöntemle yapsaydım, havaya 32 bitin tamamını dönecektim.

Kod Örneği

Mantığı koda dökmek de bayağı basit. Go ile şöyle bir fonksiyon yazdım:

func countSetBits(n int) int {
    count := 0
    for n > 0 {
        n = n & (n - 1) // En sağdaki 1 bitini yok et
        count++         // Sayacı artır
    }
    return count
}

Karmaşıklık Analizi (Complexity Analysis)

  • Zaman Karmaşıklığı (Time Complexity): O(k) – Buradaki k, sayının binary halindeki “1” (set bit) sayısı. En kötü senaryoda (sayının tüm bitleri 1 ise) yine O(bit_sayısı) oluyor ama ortalamada brute-force yönteminden çok daha hızlı.
  • Alan Karmaşıklığı (Space Complexity): O(1) – Ekstra bellek kullanımı yok, işlemler doğrudan CPU yazmaçları (registers) üzerinde dönüyor.

Son Söz

Yazılım mühendisliğinde optimizasyon, her zaman sisteme RAM veya CPU basmak demek değil. Bazen matematiğin ve bitlerin doğasını doğru kullanınca iş çözülüyor. Brian Kernighan Algoritması da kaba kuvvet çözümler yerine bitlerin dilini konuşarak büyük farklar yaratabileceğimizin en temiz kanıtlarından biri. Mülakatlarda falan karşınıza çıkarsa hayat kurtarır.