請解釋Kernighan的位計數算法背後的邏輯

這個問題直接通過 Bits counting algorithm (Brian Kernighan) in an integer time complexity閱讀後。有問題的Java代碼是請解釋Kernighan的位計數算法背後的邏輯

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

我想了解什麼n &= (n-1)在這裏實現？我已經看到了類似的一種結構的另一個漂亮的算法，用於檢測一個數是否是2類似於電源：

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

來源

2012-09-12 Geek

[比特中的整數時間複雜度計算算法（布萊恩·柯林漢）]（的可能的複製http://stackoverflow.com/questions/12380478/bits-counting-algorithm-brian- kernighan在整數時間複雜性） – OhadR

步進通過代碼在調試器幫助了我。

如果你開始

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

所以這個迭代4次。每次迭代以這樣的方式遞減該值，使得設置爲1的最低有效位消失。

遞減一位翻轉最低位和每位直到第一位。例如如果你有1000 .... 0000 -1 = 0111 .... 1111無論它有多少位需要翻轉，它在那裏停止，其他任何位都不變。當你和n設置的最低位和最低位變爲0

來源

2012-09-12 07:23:42

你很快，只是通過幾乎相同的描述中途:) – pap

@pap我跳轉到問題相當快，應該停止。 ;） –

原因是'1000 ... - 1 = 0111 ...'這樣按位，給你'0000 ...' – verdesmarald

從一個數字中減去1可以切換所有位（從右到左）直到最右邊的位（包括最右邊的位）。所以如果我們用1減去一個數字，然後按&與它本身(n & (n-1))進行比較，我們將取最右邊的位置1。這樣我們可以在循環中從右到左逐個取消1。

循環迭代次數等於設置的位數位。

來源：Brian Kernighan's Algorithm

來源

2017-04-10 02:54:22

請解釋Kernighan的位計數算法背後的邏輯

回答

相關問題