2014/4/9

計算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;
}

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