부호없는 정수의 비트 수를 계산하십시오.

Question

bitCount()이라는 함수를 부호없는 정수 인수의 이진 표현에서 비트 수를 반환하는 bitcount.c 파일에 작성하고 싶습니다. 여기

는 내가 지금까지 무엇을 가지고 : 난 그냥이 프로그램을 실행할 때

#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 비트 정수로 하드 코딩됩니다.