bit counting

 

어떤 값의 존재 유무만 표시할 때 종종 bit를 on off 시켜셔 표현하는 경우가 있다.

메모리가 흔해지긴 했지만 여전히 메모리는 다른 것과 비교해서 값비싼 자원이기도 하고

경우에 따라서 속도 문제때문에 사용하기도 한다.

 

정수형 변수 하나에 최대 32개 값을 on off 시킬수 있는데

가끔 이 정수 변수에 on되어 있는 값의 개수를 counting 할 필요가 생긴다.

 

예전에 해커들이 사용한다는 방법을 본적이 있긴한데

불현듯 좀 쉽고 직관적인 방법이 생각이 나서 코딩을 해보았다.

 

나중에 안 사실이지만 내가 생각한 방법이 이미 코드화 되어 있었다( 하늘아래 새로운 것이 없다더니 )

 

간단히 웹에 공개된 코드를 설명하면 BitsSetTable256배열에 1 ~ 255까지 값에 1로 set된 비트가 몇개인지 미리 테이블로 만들어 놓는것이다.

 

 

static const unsigned char BitsSetTable256[] =
{
    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
};

int bitcount ( unsigned int n )
{
    return BitsSetTable256[n  & 0xFFU]
        + BitsSetTable256[(n >>  8 ) & 0xFFU]
        + BitsSetTable256[(n >> 16) & 0xFFU]
        + BitsSetTable256[(n >> 24) & 0xFFU] ;
}