[C] 1비트수 세기

첫 번째 방법은 2로 나누어 가면서 나머지가 1인것의 개수를 세는 방법이다.

가장 단순한 방법이다.

int BitCnt1(int v){
   int cnt = 0;
   while (v){
       cnt += v % 2;
       v /= 2;
   }
   return cnt;
}

두 번째 방법은 2로 나누는것을 비트연산을 통해 조금더 빠르게 개선한 방법이다.

int BitCnt2(int v){
   int cnt = 0;
   while (v){
       cnt += (v & 1);
       v >>= 1;
   }
   return cnt;
}

세 번째 방법은 어떤수 N 과 N-1을 and연산을 취하면, 맨 오른쪽 비트가 사라지는 특성을 이용한 방법이다.

앞선 두 방법보다는 시간향상이 확실히 있다.

int BitCnt3(int v){
   int cnt = 0;
   while (v){
       v = v&(v - 1);
       cnt++;
   }
   return cnt;
}

네 번째 방법은 분할정복을 이용한 방법이다.

처음 이 소스를 보면 이게 뭐냐... 할 수 있지만 알고보면 쉽다.

우선

0x55555555 는 이진수로 01010101010101010101010101010101

0x33333333 은 이진수로 00110011001100110011001100110011

0x0f0f0f0f 는 이진수로 00001111000011110000111100001111

0x00ff00ff 는 이진수로 00000000111111110000000011111111

0x0000ffff 는 이진수로 00000000000000001111111111111111

어떠한 정수 N이 이진수로 보았을때
00100111 이라면 (설명하기 쉽게 8비트 정수로 설명 하겠다.)

분할정복 알고리즘에 따라 처음에는 인접한 1 비트를 10진수화 하여 더한다.

0+0``1+0``0+1``1+1

고로

0 , 1, 1, 2 의 결과가 나오고 이를 다시 2진수로 보면

00010110 이 된다.

이 연산에서Carry는 절대 발생하지 않는다.

이번에는 인접한 2비트를 10진수화 하여 더한다. 이러한 알고리즘을 반복한다.

00+01``01+10 => 1,3

이진수로 적으면 00010011

마지막으로 4비트를 더하면
0001 + 0011 => 4

답이 나왔다. 1의 개수는 4이다.

int BitCnt4(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);
   v = (v & 0x0000ffff) + ((v >> 16) & 0x0000ffff);
   return v;
}

다섯번째 방법 은 하드웨어 명령을 이용한 방법이다.

이 방법보다 빠를 순 없다.

Visual Studio

#include<intrin.h>    //__popcnt
int BitCnt5(int v){
 return __popcnt(v);
}

gcc

#include<stdio.h>
int main(){
        int n=__builtin_popcount(7);
        printf("%d\n",n);
        return 0;
}