bit count. 비트 수 세기

Stack overflow에 따르면 해당 숫자를 2진법으로 표현했을 때 1의 갯수를 세는 가장 빠른 함수는 다음과 같다.

int numberOfSetBits(uint32_t i)
{
     // Java: use int, and use >>> instead of >>. Or use Integer.bitCount()
     // C or C++: use uint32_t
     i = i - ((i >> 1) & 0x55555555);        // add pairs of bits
     i = (i & 0x33333333) + ((i >> 2) & 0x33333333);  // quads
     i = (i + (i >> 4)) & 0x0F0F0F0F;        // groups of 8
     return (i * 0x01010101) >> 24;          // horizontal sum of bytes
}

출처 : https://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer

해당 코드보다 더 와닿는 코드는 다음과 같다. 분할정복을 이용한 방식이다.

int BitCount(int i){
   i = (i & 0x55555555) + ((i >> 1) & 0x55555555);
   i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
   i = (i & 0x0f0f0f0f) + ((i >> 4) & 0x0f0f0f0f);
   i = (i & 0x00ff00ff) + ((i >> 8) & 0x00ff00ff);
   i = (i & 0x0000ffff) + ((i >> 16) & 0x0000ffff);
   return i;
}

16진법을 2진법으로 나타내면 다음과 같다.

0x55555555 는 이진수로 01010101...의 형태이고
0x33333333는 이진수로 00110011...의 형태이고
0x0f0f0f0f는 이진수로 0000111100001111...의 형태이고
0x0000ffff는 이진수로 0000 0000 0000 0000 1111 1111 1111 1111이다.

해당 숫자들과 & 연산을 한다는 것은 인접한 비트를 10진수화 해서 더하는 것을 의미한다.
예를 들어 어떤 숫자가 01000111이면,
두개씩 묶어 0+1 / 0+0 / 0+1 / 1+1 이 되고 이는 10진수화 시켰을 때 1,0,1,2가 된다.
이를 다시 2진수로 보면 01000110이 된다.
이번에는 인접한 2비트를 10진수화 하여 더하면 01+00 / 01+10 이고 이는 1,3이 된다.
이를 2진수로 적으면 00010011이다.
마지막으로 4비트를 더하면 0001 + 0011 = 4이고,
1의 갯수는 4이다.