Kernighan'ın bit sayım algoritmasının ardındaki mantığı açıklayınız.

Question

Bu soru, Bits counting algorithm (Brian Kernighan) in an integer time complexity üzerinden okuduktan sonra doğrudan izler. Söz konusu Java kodu burada elde ne n &= (n-1) anlamak istiyorum

int count_set_bits(int n) { 
    int count = 0; 
    while(n != 0) { 
     n &= (n-1); 
     count++; 
    } 
} 

mı? Bir numara 2 gibi bir güç olup olmadığını tespit etmek için başka şık algoritmasında yapının benzer türde bir gördük: Bir hata ayıklayıcı bana yardımcı içinde

if(n & (n-1) == 0) { 
    System.out.println("The number is a power of 2"); 
} 

Answer 1

kod üzerinden atlama.

So

n = 1010101 & n-1=1010100 => 1010100 
n = 1010100 & n-1=1010011 => 1010000 
n = 1010000 & n-1=1001111 => 1000000 
n = 1000000 & n-1=0111111 => 0000000 

bu yineler 4 kez ile başlayın. Her yineleme, değeri 1'e ayarlanan en az anlamlı bitin yok olacağı şekilde değeri azaltır.

Bir azaltma, en düşük biti ve her biti ilk olana kadar çevirir. Örneğin. Eğer 1000 varsa .... 0000 -1 = 0111 .... 1111 ne kadar bit yapması farketmez ve orada durur ve diğer bitler el değmeden bırakılır. n ile siz ve bu düşük bit var ve sadece en düşük bit bir dizi 1 0

Answer 2

Çıkarma (righmost set bit dahil) en sağdaki set bit kadar (sağdan sola) tüm bitlerini değiştirir hale gelir. Eğer bir sayıyı 1 ile çıkarırsak ve 'u kendi başına (n & (n-1)) ile yaparsak, en son ayarlanmış biti kaldırırız. Bu şekilde, 1'leri döngüden sağdan sola doğru tek tek çözebiliriz.

Döngü yineleme sayısı, bit kümelerinin sayısına eşittir.

Kaynak: Brian Kernighan's Algorithm

[bir tamsayıdır zaman karmaşıklığı algoritma (Brian Kernighan) sayılması Bit] (arasında