[C/C++] count 1 bits of input value by shifting.

之前寫了一篇:『[C/C++] 計算二進位任意數含有多少個位元為1?』,裡面用 n &= (n – 1); 的方式來計算二進位數字總共會得到多少 bit,這次來紀錄利用 shift 方式也可以得到總共含有多少 bit 數目,函式如下:
#include 
#include 
int count_1_bit_count(unsigned int);
int main(){
    int count = 0, a;
    a = 1023;
    count = count_1_bit_count(a);
    printf("%d有%d個位元為1\n\n", a, count);
    system("pause");
    return 0;
}
int count_1_bit_count(unsigned int n)
{
    int count = 0;
    for(count = 0; n != 0; n >>= 1L)
    {    
        if(n & 0x01)
            count++;
    }    
    return count;
}
關鍵就是在 n >>= 1L,把該數字往右位移 1 bit,然後跟 0x01 去做 and,如果數字大於0,count 就加 1。
  • Solomon

    「然後跟 0×01 去做相乘」相乘應為AND。

  • Dear Solomon:
    I correct mistakes,thanks of your remind.

  • idreamer

    我以前才查過這個問題的寫法,如果查表法不算的話,還有底下兩種:
    unsigned int bitcount(unsigned int v)
    {
    v = v – ((v >> 1) & 0x55555555);
    v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
    return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
    }

    unsigned int numbits(unsigned int v)
    {
    v = (v & 0x55555555) + ((v >> 1) & 0x55555555);
    v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
    v = (v & 0x0f0f0f0f) + ((v >> 4) & 0x0f0f0f0f);
    v = (v & 0x00ff00ff) + ((v >> 8) & 0x00ff00ff);
    return (v & 0x0000ffff) + ((v >> 16) & 0x0000ffff);
    }
    提供您參考一下。不過根據我們之前實驗的結果,查表法最快。 XD