← tüm yazılar
037

Bit Manipülasyonu ile O(1) Optimizasyonu: Number Complement Çözümü

Yazılım mülakatlarında ya da günlük hayatta performans kritik işlerle uğraşırken karşımıza sıkça çıkan bir konu var: Bit manipülasyonu. Genellikle bu tarz soruları gördüğümüzde aklımıza ilk gelen çözüm, sayıyı string’e veya bir array’e çevirip üzerinde dönmek oluyor. Ancak bu yaklaşım, farkında olmadan kodumuza devasa bir “overengineering” (aşırı mühendislik) yükü getiriyor.

Bu yazıda, LeetCode’daki 476. Number Complement sorusu üzerinden, bir sayının bit seviyesindeki tümleyenini (complement) bulurken yapılan yaygın hataları ve bu işi CPU seviyesinde O(1) karmaşıklıkla nasıl en optimal hale getirebileceğimizi konuşacağız.

Problem Ne?

Elimizde bir tamsayı var ve bizden bu sayının binary (ikilik) temsilindeki tüm 0’ları 1, tüm 1’leri ise 0 yapmamız isteniyor.

Örneğin sayımız 5 olsun. Binary karşılığı 101. Bunun complement’i 010, yani onluk tabanda 2 olmalı.

Buradaki en kritik nokta şu: Bilgisayar mimarisinde tam sayılar hafızada sabit bit genişliklerinde (örneğin 32-bit) tutulur. Dolayısıyla 5 sayısı aslında hafızada şöyle durur:

Plaintext

00000000 00000000 00000000 00000101  <- Toplam 32 bit
|_______________________|  |_|
     Önemsiz Sıfırlar       Anlamlı Bitler (Bizi ilgilendiren kısım)
    (Leading Zeros)

Eğer sayının doğrudan bitwise NOT (~) operatörüyle tersini alırsak, sol taraftaki o önemsiz sıfırlar da 1’e dönüşeceği için bambaşka ve devasa bir sayı elde ederiz. Hedefimiz sol taraftaki “leading zeros” dediğimiz önemsiz sıfırlara dokunmadan, sadece anlamlı bitleri tersine çevirmek.

İlk Refleks: Slice/Array Kullanarak Çözmek (Neden Yanlış?)

Bu problemi çözmek için ilk başta bir []byte slice’ı oluşturup, bitleri sağa kaydırarak tek tek bu array’e append etmeyi, ardından bu array’i tekrar int‘e çevirmeyi düşünebiliriz.

Kod çalışır mı? Evet, mantık hatası yapmazsak çalışır. Ancak kıdemli bir mühendis gözüyle baktığımızda bu çözüm sınıfta kalır:

  • Gereksiz Hafıza (Space Complexity): Sadece bir sayıyı dönüştürmek için hafızada (heap) dynamic array allocation yapıyoruz. Bit sorularında hedefimiz her zaman O(1) space olmalı.
  • Hata Riski (Bug Prone): Döngüler, pointer kaydırmalar ve flag kontrolleri işin içine girdiğinde kodun okunabilirliği düşer ve “infinite loop” gibi hatalara davetiye çıkarız.

Optimizasyon: Standart Kütüphane ve Donanım Desteği

Peki, sol taraftaki o önemsiz sıfırları bir döngü yazıp tek tek saymadan nasıl geçebiliriz? İşte burada Go’nun standart kütüphanesindeki math/bits paketi imdadımıza yetişiyor.

bits.Len(uint(num)) fonksiyonu, sayının binary temsilindeki anlamlı bit uzunluğunu bize verir. Arka planda yaptığı iş aslında şudur: Toplam bit genişliğinden (32), sol taraftaki önemsiz sıfırların (leading zeros) sayısını çıkarmak.

En güzel tarafı ise bu fonksiyon arka planda bir for döngüsü döndürmez. Modern işlemcilerde (Intel, AMD, ARM) bu işlemi tek bir saat çevriminde (single CPU cycle) yapan özel donanım komutları bulunur. Go derleyicisi bu fonksiyonu doğrudan işlemci seviyesindeki LZCNT (Count Leading Zeros) veya CLZ komutlarına dönüştürür. Yani donanım avantajını kullanarak O(1) zamanda en anlamlı bitin konumunu öğreniriz.

En Optimal Çözüm: XOR Sırrı

Anlamlı bitlerin uzunluğunu öğrendikten sonra, array yaratmaya veya bitleri tek tek dönmeye ihtiyacımız kalmıyor. Bitleri tersine çevirmek (0->1, 1->0) demek, o sayıyı tamamen 1’lerden oluşan bir “Maske” ile XOR işlemine sokmak demektir.

XOR kuralı basittir: Bitler farklıysa 1, aynıysa 0 üretir. Bir biti 1 ile XOR’larsanız, o bit otomatik olarak tersine döner.

Gelin bunu koda dökelim:

Go

package main

import "math/bits"

func findComplement(num int) int {
    // 1. Sayının binary'de kaç bit kapladığını bul (CPU seviyesinde O(1))
    // Örn: num = 5 (101) ise bitLength = 3 olur.
    bitLength := bits.Len(uint(num))
    
    // 2. O bit uzunluğunda, tamamen 1'lerden oluşan bir maske yarat
    // 1 << 3  => 1000 (Binary)
    // 1000 - 1 => 0111 (Binary) -> Yani maskemiz 7
    mask := (1 << bitLength) - 1
    
    // 3. Sayı ile maskeyi XOR'la ve bitleri tek hamlede tersine çevir
    // 101 (5)
    // 111 (7)
    // ^ -----
    // 010 (2)
    return num ^ mask
}

Bu Çözüm Bize Ne Kazandırdı?

  • Time Complexity: O(1) — Herhangi bir loop veya iterative işlem yok. CPU seviyesinde birkaç temel instruction ile bitiyor.
  • Space Complexity: O(1) — Ekstra hiçbir veri yapısı, array veya slice allocate edilmedi. Bellek dostu.
  • Maintainability: Sadece 3 satır kod, sıfır karmaşıklık ve sıfır bug riski.

Özet

Yazılım geliştirirken yapısal veri yapılarına (arrays, maps, strings) çok alışkınız ve her problemi bunlarla çözmeye meyilliyiz. Ancak alt seviye (low-level) problemlerde veya performans kritik algoritmalarda, dilin bize sunduğu bitwise operatörleri ve donanım destekli standart kütüphane fonksiyonlarını kullanmak, bizi hem tonlarca kod yazmaktan kurtarır hem de sistem kaynaklarını en verimli şekilde kullanmamızı sağlar.

Bir sonraki yazıda görüşmek üzere.

Yorum bırak