December 31, 2011 - Tagged as: python, java, lisp, tr.
Bugün çok fantastik birşey gördüm, anlatmazsam ölürüm(uygun bir başlık düşünmem tüm yazıyı yazmamdan daha uzun sürdü o yüzden idare edin hehe).
Diyelim ki bir veri yapısı tasarlıyoruz, bir nodedan bir sürü başka nodea veya elemana pointerlar olacak. Bir yandan da bellek kullanımını minimum tutmak istiyoruz. Pointerları tutan arrayimizde hiç boş yer olmamalı.
Bir bitmap tutuyoruz. Büyük ihtimalle integer oluyor(Java primitive int tipi 32bit olmak zorunda mesela). Diyelim ki bu node’un n. indexine bir eleman/pointer ekleyeceksiniz. Bitmap ilk başta 0 tabii. Şu şekilde bitmap’de ilgili elemanı 1 yapıyoruz:
bmp = bmp | 1 << nBuraya kadar herşey çok basit. Bu noktadan sonra bu bitmape göre 30. elemanın arrayde nereye denk geldiğini bulmamız lazım. Bunun için şu formülü kullanıyoruz:
ctpop(bmp & ((1<<n)-1))ctpop, population count fonksiyonu, yani bir sayının iki tabanında gösterilişindeki 1 bitleri sayıyor. Bu Java’da Integer.bitCount fonksiyonu(öhm, static methodu) ile bulunabilir.
Birkaç deneme yaparak nasıl yaptığını anlayabilir ve kendimizi ikna edebiliriz:
In [^2]: bmp = 0
In [^3]: bmp |= 1 << 15
In [^4]: ctpop(bmp & ((1<<15)-1))
Out[^4]: 0
In [^5]: bmp |= 1 << 21
In [^6]: bmp |= 1 << 10
In [^7]: ctpop(bmp & ((1<<10)-1))
Out[^7]: 0
In [^8]: ctpop(bmp & ((1<<15)-1))
Out[^8]: 1
In [^9]: ctpop(bmp & ((1<<21)-1))
Out[^9]: 2Eğer arraydeki n. yere bir eleman ekliyorsak, n’den itibaren arrayi bir kaydırmamız lazım. En büyük index her zaman arrayde de daha sonda oluyor.
Ne yaptığına bakalım. 25. elemanın arraydeki yerine bakarken, 1 << 25i hesaplıyorum ki bu aslında (2 tabanında) 1 ve yanına 25 tane 0 koymak demek. Daha sonra bu sayıdan 1 çıkararak, en sağdan itibaren(en anlamsız bitten itibaren) tüm 0ları 1 yapıyorum, ilk gördüğüm 1’i 0 yapıyorum, gerisine dokunmuyorum(bu şartlar altında geriye kalan tüm bitler 0 oluyor). Daha sonra bu sayı ile bitmap’i logical and(bazı yerlerde bitwise and diyor, aynı şeyler sanırım?) işlemine sokup ctpop yaptığımda, bitmap’de (1 << n)’den itibaren kaç tane 1 olduğunu saymış oluyorum ve bu da bana array’deki indeximi veriyor. Çok mantıklı.
Bu arada kullandığınız dile göre bu işlemi daha kolay bir şekilde yapabilirsiniz. Bazı diller(Java’da Integer.bitcount, Common Lisp’de logcount gibi) direkt olarak bitCount gibi fonksiyonlar sunuyor. Bir de ben Common Lisp’de hiç kaydır 1 çıkart falan demeden direkt “şu bitle şu bit arasında kaç 1 olduğunu say” şeklinde bir fonksiyon yazdım, bitwise trickler yapmadan, şöyle:
(defun ctpop (bitmap &key (start 0) (end 32))
(logcount (ldb (byte (- end start) start) bitmap)))