O(1)로 비트 갯수 세는 알고리즘 세가지

int countBits(unsigned int x) {
	unsigned int y = x - ((x >> 1) & 033333333333) - ((x >> 2) & 011111111111);
	return ((y + (y >> 3)) & 030707070707) % 63;
}

긴 상수들은 앞에 0이 붙어있으므로 8진수이다.

 

어지럽다.......

 

반환문을 아래와 같이 고쳐서 mod연산보다 속도가 빠른 비트연산을 사용할 수도 있다.

int countBits(unsigned int x) {
	unsigned int y = x - ((x >> 1) & 033333333333) - ((x >> 2) & 011111111111);
	y = ((y + (y >> 3)) & 030707070707);
    return ((y * 0404040404) >> 26) + (y >> 30);
}

 

 

 

 

속도를 원하면서 코드를 (굳이)외워서 사용하고싶다면

가독성이 (그나마) 좋은 아래 코드를 사용하면 될 것 같다.

O(1)이지만 RISC 기준 명령 19개를 사용한다.

맨 처음에 소개한 코드는 (unsigned 나머지 명령이 하나의 명령어라는 가정 하에) 명령 13개가 필요하다.

int countBits(unsigned int x){
	unsigned int n;
    
    n = (x >> 1) & 0x77777777;
    x -= n;
    n = (x >> 1) & 0x77777777;
    x -= n;
    n = (x >> 1) & 0x77777777;
    x -= n;
    
    x = (x + (x >> 4)) & 0x0F0F0F0F;
    x *= 0x01010101
    
    return x >> 24;
}

 

 

속도를 포기하고 이해하기 편한 O(n) 알고리즘을 택한다면

이 코드가 최선인 것 같다.

int count(int n) {
    int i;
    for (i = 0; n != 0; i++) n &= n - 1;

    return i;
}