通過取消最右邊位來計算奇偶校驗

Question

計算奇偶校驗的第一種方法是對每一位執行異或運算。 - 這很容易理解。 到的增強是丟棄低位並保持反轉奇偶校驗，直到數變爲0 即

While loop till number is greater than 0 
1) parity = parity^1 
2) number = number & (number-1) 

這是如何工作的？我猜想要掌握這種方法的想法有點困難。

Answer 1

所以一旦你看到什麼number &= number - 1是，這樣做的問題是微不足道的。下面是一個二進制例如：

first pass 
1001001 - 1 = 1001000 
1001001 & 1001000 = 1001000 

second pass 
1001000 - 1 = 1000111 
1001000 & 1000111 = 1000000 

third pass 
1000000 - 1 = 111111 
1000000 & 111111 = 0 

注意，它需要把數字變成零的遍數，相當於設置位的數量，因爲你刪除一個設置的比特每遍。奇偶校驗是模數2的置位數（或總和）。模2的加法是異或操作，因此在算法中使用異或來尋找奇偶校驗。