計算無​​符號整數中的位數

Question

我想在文件bitcount.c中編寫一個名爲bitCount()的函數，該函數返回無符號整數參數二進制表示中的位數。

這是我到目前爲止有：

#include <stdio.h> 

int bitCount (unsigned int n); 

int main() { 
    printf ("# 1-bits in base 2 representation of %u = %d, should be 0\n", 
     0, bitCount (0)); 
    printf ("# 1-bits in base 2 representation of %u = %d, should be 1\n", 
     1, bitCount (1)); 
    printf ("# 1-bits in base 2 representation of %u = %d, should be 16\n", 
     2863311530u, bitCount (2863311530u)); 
    printf ("# 1-bits in base 2 representation of %u = %d, should be 1\n", 
     536870912, bitCount (536870912)); 
    printf ("# 1-bits in base 2 representation of %u = %d, should be 32\n", 
     4294967295u, bitCount (4294967295u)); 
    return 0; 
} 

int bitCount (unsigned int n) { 
    /* your code here */ 
} 

好吧，當我運行此我得到：

# 1-bits in base 2 representation of 0 = 1, should be 0 
# 1-bits in base 2 representation of 1 = 56, should be 1 
# 1-bits in base 2 representation of 2863311530 = 57, should be 16 
# 1-bits in base 2 representation of 536870912 = 67, should be 1 
# 1-bits in base 2 representation of 4294967295 = 65, should be 32 

RUN SUCCESSFUL (total time: 14ms) 

不退還位的正確數目。

返回C中無符號整數參數二進制表示形式的位數的最佳方法是什麼？

Answer 1

int bitCount(unsigned int n) { 

    int counter = 0; 
    while(n) { 
     counter += n % 2; 
     n >>= 1; 
    } 
    return counter; 
} 

Answer 2

原來，有一些相當複雜的方法來計算這個答案爲here。

下面的impl（我學會了回來）簡單地循環敲掉每次迭代中最不重要的位。

int bitCount(unsigned int n) { 

    int counter = 0; 
    while(n) { 
    counter ++; 
    n &= (n - 1); 
    } 
    return counter; 
} 

Answer 3

這是一個不需要迭代的解決方案。它利用了以下事實：在二進制中添加位完全獨立於位的位置，並且總和不超過2位。 00+00=00，00+01=01，01+00=01,01+01=10。第一個添加同時添加16個不同的1位值，第二個添加8個2位值，並且每個添加一半的值，直到剩下一個值。

int bitCount(unsigned int n) 
{ 
    n = ((0xaaaaaaaa & n) >> 1) + (0x55555555 & n); 
    n = ((0xcccccccc & n) >> 2) + (0x33333333 & n); 
    n = ((0xf0f0f0f0 & n) >> 4) + (0x0f0f0f0f & n); 
    n = ((0xff00ff00 & n) >> 8) + (0x00ff00ff & n); 
    n = ((0xffff0000 & n) >> 16) + (0x0000ffff & n); 
    return n; 
} 

這是硬編碼爲32位整數，如果你是一個不同的大小，它將需要調整。