Counting One Bits

Kategori: Popular Algorithms , 19 Kasım 2019 , JanFranco


Problem:

Bir binary sayıdaki 1 bitlerin sayısını bulmak istiyoruz.

Yaklaşım:

Bu problemi çözebilecek en pratik çözüm x &= x - 1 işlemidir. 170 sayısında bunu deneyelim. 170 binary olarak 10101010 şeklinde yazılır. 10101010 - 1 = 10101001. 10101010 & 10101001 = 10101000. x &= x - 1 işlemini bir kez gerçekleştirdik. Bu durumda n = 1 olsun. 10101000 - 1 = 10100111. 10101000 & 10100111 = 10100000. n = 2 oldu. 10100000 - 1 = 10011111. 10100000 & 10011111 = 1000000. n = 3 oldu. 1000000 - 1 = 111111. 1000000 & 0111111 = 0000000. n = 4 oldu ve elimizdeki sayı artık sıfır olduğuna göre durabiliriz. Başlangıçtaki sayımız 10101010 idi ve toplam 1 bit sayısı dörttü. n değerimiz de 4. Oldukça basit, pratik.

Çözüm:




def count_1s(value):
    n = 0
    while value:
        value &= value - 1
        n += 1
    return n

print(count_1s(0b10101010)) # 170


Sonraki Yazı: Merge Sort Algorithm
Yorumlar

Henüz bir yorum bulunmuyor.
Yorum bırakın