int형 변수에서 1인 비트수(비트개수) 구하기

1. 가장 단순한 방법

unsigned int v;

unsigned int c; // v의 1인 비트 수

for (c = 0; v; v >>= 1) c+= v & 1;

// unsigned int의 비트수 만큼 for문을 돔

2. 좀더 나은 방법

unsigned int v;

unsigned int c; // v의 1인 비트 수

for (c = 0; v; ++c) v &= v - 1;

// v의 1인 비트 수 만큼 for문을 돔

3. 신기한 방법

unsigned int v;

unsigned int c;

// 32비트 정수형에 최적화된 코드

v = v - ((v >> 1) & 0x55555555);

v = (v & 0x33333333) + ((v >> 2) & 0x33333333);

c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;

// 128비트 정수형까지 커버 가능한 코드

typedef unsigned int T;

T v;

unsigned int c;

v = v - ((v >> 1) & (T)~(T)0/3);

v = (v & (T)~(T)0/15*3) + ((v >> 2) & (T)~(T)0/15*3); 

v = (v + (v >> 4)) & (T)~(T)0/255*15;

c = (T)(v * ((T)~(T)0/255)) >> (sizeof(T) - 1) * CHAR_BIT;

// CHAR_BIT 는 char의 비트수

출처 : http://graphics.stanford.edu/~seander/bithacks.html