CP #36: Python Bitwise Islemler

Bitwise islemlere gecmeden once, int tipi ile alakli bir hatirlatma yapalim.

Python3'ten itibaren, int tipinin tutabilecegi max deger, bilgisayar hafizasi kadardir. Yani tipin kendisinde bir kisitlama yok. Bu da demek oluyor ki, yeterince hafiza varsa sistemde, int tipini overflow etmek imkansizdir. Bunu nasil basariyor peki? 

Arbitrary Precision
Python 2.0'da tam sayilar icin iki farkli tip vardi: int ve long. Buradaki int, C data typi olup, sabit "precision"a sahiptir. Yani kodun calistigi platforma gore 2 veya 4 byte ile temsil edilir ve buna bagli olarak tutabilecegi maksimum deger bellidir (detaylara suradan bakabilirsiniz). Dogal olarak bu tip overflow edilebilir. Hatta sys.maxint ile kodun calistigi platformda, int tipinin alabilecegi max degere ulasabilirz. Ama Python2 bile, bunu guzel bir sekilde handle etmektedir. Eget int tipi overflow oluyor ise, otomatik olarak long'a "promote" edilir. 

Python3'te int tipi ve long tipi birlestirilerek sadece arbitrary precision implementasyou geriye kalmistir. Haliyle sys.maxint sabit degeri kaldirilmis, bunun yerine sys.maxsize getirilmistir. Neden? Anladik ki int tipinde bir sinir yok, peki ben list index karsilastirmasi icin cok buyuk buyuk bir index degeri almak istesem neyi referans sececegim? Int'te limit yok ama bir liste ya da daha genel olarak tum sequence tiplerinin tutabilecegi max eleman sayisinda limit var. Bu da sys.maxsize ile tanimlanmis. Yani sys.maxsize ile hicbir list veya seq tipinden bir indexe ulasamayiz, hepsi de index hatasi verir. 

Yani bir int degerinin kac hane ile temsil edileceginin bir siniri olmadigindan hafiza yettigi surece overflow olma inhitimali yoktur. 

Bit Manipulasyonu

Simdi hep birlikte aslinda en temelde neler oluyor bir bakalim. Bu kisim buyuk olcude Competitive Programmers Handbook kitabinin 10. chapterinden aldigim notlardan olusmaktadir.

Bilgisayarda tum veriler bitler (1 ve 0) sekilde tutulmaktadir. Ayni sekilde bir int deger de hafizada 1 ve 0lar seklinde tutulur. Kac bit ile temsil edilecegi ise yukarida bahsettigimiz fixed veya arbitrary precision ile alakalidir. Simdilik biz n bit integer dedigimizde n adet bit ile temsil edilen bir integer anlayalim. Ornegin 43 sayisini 32bit sekilde ifade edecek olursak:

00000000000000000000000000101011

seklinde ifade edebiliriz. Bir integer signed veya unsigned olabilir. Eger signed olursa, pozitif ve negatif degerler tutabilir. Bu durumda -2^(n-1) ile +2^(n-1) arasinda degerler alabilir. Neden? Cunku en bastaki 1 biti sayinin isaretini (arti mi eksi mi) tutmak icin harcamis oluyoruz. Bu en bastaki bite ise integerin pozitif mi yoksa negatif mi oldugunu belirleyen "sign-bit" adi verilmektedir. 

Unsigned int icin ise sign-bit gerekmediginden, bu biti de sayilari temsil etmede kullanabiliriz. Bu sayede unsigned bir int, 2^n - 1 kadar olan degerleri tutabilir. Neden 1 cikartiyoruz? Diyelim 2 bitlik bir int var elimizde, alabilecegi en buyuk deger 3tur. Yani 2^2 - 1.  

Bit Islemleri

Iki binary sayi uzerinde yapilabilecek islemlere bir gozatalim.

And Operatoru ( & )
Verilen iki binary sayi icin, ikisinin de 1'e sahip oldugu basamaklar 1 degerini alir. Eger ikisinden birisi 0 ise, o basamak icin sonuc 0 olur. Bildigimiz `and` operatoru iste. 

And operatoru kullanarak, bir sayinin cift mi tek mi oldugunu cok rahat anlayabiliriz. Sayiyi  binary olarak dusunecek olursak, son basamagi 0 ise cift, 1 ise tek olacaktir. Son basamagi kontrol etmek icin 1 ile and operatorune sokulup, sonuca bakarsak, eger sayi cift ise sonuc 0, tek ise 1 olacaktir. Ornegin 5 icin 5 & 1 islemi soyle bir sey oluyor:

       ...00101
&    ...00001
----------------
       ...00001 --> 1

Yani ozetle:

x & 1 == 1 # x, cift
x & 1 == 0 # x, tek

Ve daha da genel bakacak olursak, bir x sayisi icin eger x & (2^k - 1) = 0 ise, x sayisi 2^k ile kalansiz bolunabilir.

Or Operatoru ( | )
Bildiginiz or opratoru olup, verilen iki binary sayida, bir basamakta ikisi de 1'e sahip ise basamak degeri 1 olur. Ancak ikisi de 0'a sahip ise sonuc 0 olur. 

Xor Operatoru ( ^ )
Exclusive or olarak da adlandirilir. Yani sadece verilen iki deger farkli ise true (1) dondurur. Ornegin iki deger de 1 olursa, sonuc 0 olur. 

Not Operatoru ( ~ )
Bu da verilen bir binary ifadenin tersini almamizi saglar. 0'lar 1, 1'ler de 0 olur. 

Bit Shift
Sola ve saga olmak uzere iki adet bit kaydirma islemi vardir. Sola k adet bit-shift etmek demek, binary sayinin sonuna k adet sifir koymak demektir. Yani 5 sayisini 2 kere sola shift edersek, 

x = 00101
x << 2 => 10100

 Sonucun 20 ettigi gozlerden kacmiyor. Zaten anlayabilecegimiz uzere, bir sayisi 1 kere sola shift ettigimizde 2 ile carpmis oluyoruz aslinda. 2 kere shift edersek de 4 ile carpmis oluyoruz. Genel olarak k kadar shift ettigimizde 2^k ile carpmis oluruz. 

Benzer sekilde saga shift ettigimizde ise, sag taraftan k adet bit'i atmis oluyoruz. Yani 5'i 1 kere saga shit edersek:

x = 00101
x >> 1 => 00010

Sonuc 2 olacaktir. Bu da bize gosteriyor ki bir sayiyi k kadar saga shift etmek, 2^k'ya bolmek gibidir. Tek fark, sonucun bir integer degerine yuvarlanmis hale geliyor olmasi. Ne de olsa bitleri kaybediyoruz. 

Uygulamalar

Bit Masking
Ornegin 1 sayisini alip, sola dogru k kadar shift edersek, sonucta elde edecegimiz binary sayida k. basamak 1 olup, diger tum basamaklar sifir olacaktir. Bunu da, diger baska bir sayinin sadece k. basamagini okumak icin kullanabiliriz. Cunku sadece k. basamagi 1 olan bir sayi ile baska bir sayiyi and islemine sokarsak, diger sayinin k. basamaginin 1 mi yoksa 0 mi oldugunu direk gorebiliriz. 

Mesela bu mantik ile, verilen bir int degerin binary temsilini yazdiran bir fonksiyon yazalim. (Aslinda yazilmisi var, python bin fonksiyonu tam bu is icin).

def print_binary(num):
    mask = 1
    # binary basamaklari tutacagimiz array

    digits = []
    
    # kolaylik olsun, az yer kaplasin diye sistemi 4 bit kabul edelim

    for i in range(4):
        # bitmask ile her bir basamagi kontrol ediyoruz

        digit = num & (mask << i)
        # eger basamak 1 ise if degeri true donecektir
        # bu durumda 1 ekliyoruz, degilse 0
        if digit: digits.append("1")

        else: digits.append("0")
    # son olarak, biz basamaklari sondan basa dogru check ettik

    # ama arraya ekleme sirasi da sondan basa dogru oldu

    # bu yuzden reverse ediyoruz
    return "".join(reversed(digits))

Fonksiyonu denersek gorecegiz ki ornegin 5 icin:

0101 degerini elde ediyoruz.

K. Biti Degistirme
Yukaridaki ornekte oldugu gibi, k. biti filtreleyip sifir veya 1 mi oldugunu kontrol etmenin yaninda, bu biti istedigimiz degere (sifir veya bir) set edebiliriz. 

x | (x << k)  Or operatoru kullanarak k. biti 1'e set edebiliriz

x & ~(x << k) Or operatoru ve not operatoru ile, k. biti 0'a set edebiliriz

x ^ (x << k) Xor operatoru ile k. biti invert edebiliriz

Set Temsili
0, 1, ... n-1 seklinde n adet eleman iceren bit set icin, her bir subset n basamakli bir binary sayi ile temsil edilebilir. Her bir basamak, o indexteki elemanin sete dahil olup olmayacagini belirtir. Ornegin 4 elemanli (0, 1, 2, 3) seti icin, tum elemanlarin dahil oldugu bir subset 1111 seklinde gosterilir. Ya da sadece sonuncu elemanin oldugu bir subset 0001 seklinde gosterilir. 

Bu sekilde cok performansli bir sekilde bir set yapisi yaratabiliriz. Her bir eleman hafizada 1 bit yer kaplayacaktir ve de set islemleri bit operasyonlari seklinde implemente edilebilir. 

Ornek: (0,1,2,3) elemanlari icin 1 ve 3 elemanlarini sete ekleyelim ve nasil gorunuyor bir bakalim:

# seti temsil edecek olan sayi
set_num = 0

# 1 ve 3'u ekle
set_num |= (1 << 1)
set_num |= (1 << 3)

bin(set_num)
# 0b1010 yazacaktir. bastaki 0b kismi, binary sayi oldugunu belirtmektedir. 
# yani esas kisim 1010 kismi. burada da dikkat edersek
# sadece 1. ve 3. basamaklar 1 dir. Yani bu elemanlar sete dahildir.

Yine daha once yaptigimiz gibi, sadece 1'leri bularak da set'teki elemanlari tespit edebiliriz:

def set_items(set_num): 
    mask = 1
    items = []
    for i in range(4):
        if set_num & (mask << i): 
            items.append(i)
    return items

Madem ki bir seti binary sayi seklinde 1 ve 0 lar ile temsil ediyoruz, set islemlerini de bit opertasyonlari seklinde tanimlayabiliriz:

set birlesimi x | y
set kesisimi x & y
setin degili (complement) ~x
fark (difference) x & ~y

Ornegin x={1, 3, 4, 8} ile y={3, 6, 8, 9} setlerinin birlesimine bakalim:

x = (1 << 1) | (1 << 3) | (1 << 4) | (1 << 8)
y = (1 << 3) | (1 << 6) | (1 << 8) | (1 << 9)
x_y_union = x | y

print(set_items(x_y_union))
# sonucun {1, 3, 4, 6, 8, 9} oldugu gorebiliriz.

Tum subsetlerin bulunmasi
Madem binary sayi ile subset temsil edebiliriyoruz, binary sayi uzerinde iterasyon yaparak da 0'dan n'e kadar olan bir setin tum subsetlerini performansli bir sekilde olusturabiliriz. 

def subsets(n):
    # ilk subset hic eleman icermeyen
    sb = 0

    # subset'in ust siniri 1<<n olmaktadir.
    # cunku basamaklar 0'dan basladigi icin
    # 5 elemanli bir sette en son iterasyon adimi 1 << 4 olur
    while sb < (1 << n):
        # eger k elemanlari subsetleri olusturmak istersek burada
        # subset'in sahip oldugu eleman sayisini kontrol edebiliriz.
        # ornegin sadece 2 elemanli subsetleri yazdirmak istersek:
        # if bin(sb).count("1") == 2
        print(print_bin(sb))
        b += 1

Bunu calistirdigimizda, ornegin n=3 icin:

0000
0001

0010

0011

0100

0101

0110

0111

seklinde, tum subsetleri uretebildigimizi gorecegiz. 

Son olarak, x ile temsil edilen bir setin tum sub-setlerini olsuturalim:

def subsets_of_x(x):
    b = 0
    # x'in kendisi, yani tum elemanlari iceren subset
    print(print_bin(x))

    while (b-x)&x:
        print(print_bin(b))
        b=(b-x)&x

Ornegin {1,3} icin tum subsetler: {}, {1}, {3}, {1,3} olacaktir. 

Hamming Distance
Esit uzunluktai iki string arasinda, farkli olan karakterlerin sayisina Hamming distance adi verilmektedir. Bit stringler icin de gecerli oldugu icin, 

Hamming(1101, 1011) = 2

Olacaktir cunku 2 karakter fark var arada. 

Problem: Verilen iki binary string arasindaki Hamming Distance'i hesaplayiniz. 
Cozum: Naive yontem ile bir iterasyon icerisinde karakterleri kontrol edebiliriz. Sonucta O(n) bir islem olacaktir. Ya da, binary stringleri sayi olarak temsil edip, XOR operatoru ile ayni olmayan basamaklari bulup, sayisini dondurebiliriz. 

def hamming(s1, s2):
    # verilen bir stringi binary'e cevimemiz gerekiyor
    # bu islemi 2 defa yapacagimiz icin bir fonk. yaratalim

    def str_to_bin(s):

        num = 0

        for i in range(len(s)):

            if s[i] == "1":
                # orgenin en bastaki basamak 1 ise, yani i = 0 icin
                # sonuc binary sayida len(s) - i - 1 indexindeki bit 1 olmalidir. 

                num |= (1 << len(s)-i-1)

        return num

    

    s1_num = str_to_bin(s1)

    s2_num = str_to_bin(s2)
    # XOR operatoru ile, sadece farkli olan basamaklarin 1 olmasini sagliyoruz
    # sonucta 1'leri sayarsak, farkli olan basamaklarin sayisini bulabiliriz

    return bin((s1_num ^ s2_num)).count("1")

Ornek Problemler

1. Parity Hesabi

Bir sayinin ya da binary word diyelim, icerdigi bitlerden 1 olanlarin sayisi tek ise, bu sayinin partity degeri 1 dir. Egere icerdigi bitlerden 0 olanlarin sayisi cift ise, parity degeri 0dir. Bu islem veri transferlerinde olusan kayiplari check etme gibi kullanim alanlarina sahiptir. 

Verilen bir sayinin parity degerini hesaplayiniz. 

Cozum:

Ilk akla gelen naive yontem yine sayiyinin icindeki 1'leri saymak oluyor. Su sekilde birsey yapabiliriz:

def parity(num):

    # dondurecegimiz parity degeri sifirdan basliyor

    result = 0

    

    # sayi 0 olmadigi surece devam edecegiz

    while num:

        # num & 1 islemi ile, sayinin son basamaginini 1 mi 0 mi olduguna bakiyoruz

        # eger sayinin son basamagi 0 ise, bu ifade 0 dondurecektir. eger 1 ise 1 dondurecektir.

        # daha sonra bu degeri, result ile XOR'luyoruz :D

        # eger result 0 idi ise, ve buradan 0 gelirse, result 0 olmaya devam edecektir.

        # eger result 0 idi ise, ve buradan 1 gelirse, result 1 olacaktir.

        # yani bir nevi, result'i toggle etmis oluyoruz. 

        # nihayetide, 0'i cift sayida 1 ile XOR edersek, sonuc 0 oluyor

        # ve parity degerini dogru bir sekilde hesaplamis oluyoruz

        result ^= num & 1

        num >>= 1

    return result

Her bir adimda, sayinin sonundaki basamaga bakiyoruz ve daha sonra saga dogru 1 bit shift ediyoruz. Sonucta bitler bitince while loop'tan cikilmis olunuyor. O(n) time complexity'ye sahibiz, n burada bit sayisi. 

Bir baska yontem ise, binary sayiyi ortadan ikiye bolup, bu iki parcayi XOR operatoru ile isleme sokmak. Bu sayede binary sayi, yari uzunluga inecektir. Bu sekilde yari uzunluga indire indire gidersek, sonucta elimizde tek bir bit kalacak ve de bu parity degerini verecektir. 

def parity2(num):

    # word uzunlugunu 64 bit kabul edersek

    x ^= x >> 32
    x ^= x >> 16

    x ^= x >> 8

    x ^= x >> 4

    x ^= x >> 2

    x ^= x >> 1

    

    # elde kalan son biti okuyalim

    return x & 1

Buradaki time complexity, n word size ise log(n) olacaktir. Yukaridakine nazaran daha iyi bir cozum. 

2. Right Propagate Last 1 Bit
Verilen bir binary sayinin son 1 bitini right propagate ediniz. Ornek: 0101000 icin 0101111 dondurmesi gerekiyor. 

Cozum:
Yani en sondaki 1 bitinden sonra gelen tum basamaklar 1 olacak sekle getirmemiz gerekiyor. 

Burada verilen sayiyi ve ulasmamiz gereken sayiyi alt alta koyarsak, sondaki sifirlari nasil 1 yapabiliriz sorusu belirginlesiyor. Eldeki sayidan 1 cikartarak bunu saglayabiliriz. Daha sonra olusan bu sayi ile bastaki sayiyi OR islemine sokarsak, hedefe ulastigimizi gorebiliriz. Su videoda guzel aciklanmis.

Yani cozum tek satir ve O(1):

def right_prop(x):

    return x | (x - 1)

3. Verilen bir sayinin verilen bir 2'nin kuvvetine bolumunden kalani hesaplayiniz. Ornek: x: 77 ve pow: 6 icin 13 dondurmek gerekiyor. (Yani 77 % 64 sorunusun cevabi isteniyor)

Cozum:
Ornekteki 77 sayisini ve 2^6'yi (yani 64) binary olarak yazalim:

Elde etmemiz gereken sonuc, yani 13, sonda kalan kisim oldugu goruluyor. Yani verilen x sayisindaki en bastaki 1'i elimine etmemiz ve geri kalan sayilari dondurmemiz gerekiyor. Bunu nasil yapabiliriz? 

X sayisindan 1 cikarsak, en bastaki 1 bitine gelene kadar bir suru yol var, buyuk ihtimalle ulasamayiz o bite kadar. Ama 2^6'dan 1 cikarsak, en bastaki 1'i elimine etmis oluruz. Daha sonra da verilen x sayisi ile AND islemine sokarsak, hedefe ulasmis oluruz. 

def res_x_pow_2(x, pow):

    return x & ((1 << pow) - 1)

seklinde O(1) bir cozum elde etmis oluyoruz. 

4. Verilen x sayisinin 2'nin bir kuvveti olup olmadigini kontrol ediniz. 1, 2, 4, 8, ... icin True dondurmelidir. 

Cozum:

1, 2, 4, 8, ... sayilarina bakarsak, sonucta 2^k gibi bir genel ifadeyle gosterilebilir. Demek ki verilen x sayisini su sekillerde ise True dondurmek gerekli:

1: 0001 
2: 0010
4: 0100

8: 1000

Pattern'e bakacak olursak, verilen  sayidan 1 cikartirsak 1'in saginda kalan tum basamaklar 1 olacak ve 1'in kendisi de sifir olacaktir. Bu iki sayiyi AND islemine sokarsak, sonucta 0 elde ederiz. Ama verilen x sayisi 2'nin kuvveti degilse, ornegin 1100 gib bir sayi ise, bir cikartip, kendisini ile AND islemine sokarsak geriye:

x:              1100
x-1:           1011

x & (x-1):  1000

Gibi, sifir olmayan bir sayi kaliyor. Demek ki, sayidan 1 cikartip, kendisi ile AND'lersek, geriye sifir kaliyorsa, 2'nin kuvvetidir. 

def is_pow_2(x):

    return not x & (x - 1)

seklinde O(1) bir cozum elde ediyoruz. 

Gelecek problemlerde gorusmek uzere. Stay hungry, stay foolish, stay healthy :)