X = X & X-1 Trick

最近在寫練習的時候看到這個有趣的習題, 相信很多人已經知道了,
就是在 2's complement 裡面, X = X & X-1, 會移除 X 裡面最右邊的 1,
在 C 裡面, 只要在 unsigned (或者全為正數)的變數裡面, 就可以用這個方法,
主要原因, 我想應該是在 2 進位的體系下, 只要讓某個值少 1, 就會讓那個值最後的一個1的右邊數值產生借位, 而造成了一個很有趣的 Pattern如下:



01111111 127
01111110 126
.
.
.
01011000 88
01010111 87

所以 X & X-1 會把 least significant 1-bit 給 & 成 0.

然而, 這個方法在 Sign-and-magnitude 的表示法裡會踢到鐵板,
因為他的正負值差別只在 sign bit. 所以並不適用此規則,
ex:
10000010 -2
10000011 -3

x = -2; x &= x-1 ==> 可以看到, x 做完運算還是等於 -2.

最後來看個範例, 來計算一個 unsigned 變數裡有幾個 bit 被 turned on.

正常的方法來檢驗每個 bit

int bitcount(unsigned x)
{
int b;

for (b=0; x !=0; x >>= 1)
if (x & 01)
b++;
return b;
}

用 X & X-1 trick 來做檢驗

int quickBitcount(unsigned x)
{
int count = 0;

while (x) {
x &= (x-1);
count++;
}
return count;
}

完畢, 感謝大家收看.