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

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

#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，原理就是這麼簡單。

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

C/C++

See also