計算Bits中有多少個1

　　給定一個二進位數值計算有多少個1在裡面，這是很常見的演算問題也常常在面試中被問到（至少我的面試經驗就曾遇過一次），這個題目就個人觀點來看是驗證受測者是否理解Bit Operator。
　　最單純的想法就是每次都檢查最低位元是否為1，是的話統計值就加1，然後把所有位元都往右移一格直到待測值變成0就可以結束了，程式碼如下：

1 2 3 4 5 6 7 8 9 10 11

int count_1_bits_method1 (unsigned int val) { int cnt = 0; while (val) { if (val & 0x1) cnt += 1; val >>= 1; } return cnt; }

需要注意的是參數有用unsigned作為修飾，如果這邊是用有號數作為參數作為參數會導致無窮迴圈，原因在於右移運算子（Right Shift Operator）對於有號值的負數會作負號延展（signed extention）。

　　另一個想法則是把最低位元的1依序消除，直到數值裡面都沒有1為止，這步驟做多少次就表示有多少個1，這裡需要巧妙的使用算式N & (N - 1)，舉例8（二進位為1000b），減1後會得到7（二進位為0111b），是否觀察到因為最低位減1不夠減了所以依序向前一位數借1，直到最低的高位元是1為止（因為夠借了不需要再往上借位），將1000b與0111b做&（And Bitwise Operator）運算後就可將最低位的1給消除了，程式碼如下：

1 2 3 4 5 6 7 8 9 10

int count_1_bits_method2 (int val) { int cnt = 0; while (val) { cnt += 1; val = val & (val - 1); } return cnt; }

　　兩個演算方法最差的狀況所需時間都一樣，但平均而言第二種效率會好一些，會出這題目主要是想確定受測者能靈活運用位元運算子吧！？面試系統底層或是嵌入式相關工作應該會比較容易遇到這類考題。