[C/C++] 計算二進位任意數含有多少個位元為1?

今天看到一個有趣的題目,就是計算二進位任意數值,其中包含了幾個1,這非常有趣,利用每個 bit 做&就可以解出這個問題了:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
#include <stdlib.h>
int bitcount(unsigned int);
int main(){
    int count = 0, a;
    a = 1023;
    count = bitcount(a);
    printf("%d有%d個位元為1\n\n", a, count);

    system("pause");
    return 0;
}
int bitcount(unsigned int n)
{
   int count = 0 ;
   while (n)
   {
      count++ ;
      n &= (n - 1) ; //關鍵演算之處
   }
   return count ;
}

關鍵解法是在 n &= (n - 1) ; 這個地方,為什麼會是這樣寫呢,大家可以想看看,為什麼要 (n-1),其實可以帶數字進去跑看看就知道程式為什麼會這樣寫,這個 case 可以分作兩種,數值可能會有兩種狀況,一種是奇數,另一種就是偶數,8 代表 1000,9 代表 1001,最右邊 bit 是 1 代表奇數,剩下的都是偶數,拿9當例子帶入 while 迴圈試試看,首先將 count + 1,接下來 1001 會跟 1000 做相乘動作,就會變成 1000,接下來跑另一次 while 會變成 1000 & 0111 就會變成 0 了,退出 while 迴圈,所以結論是 (n -1) 的用意是去掉一個 1 位元 bit,就像 [xxxx10 … 0] -1 = [xxxx01 … 1] …. 每運算一次相乘,就會少掉一個 1,原理就是這麼簡單。

這只是一種解法,歡迎大家討論看看還有無其他方法?


See also