2진수 표현에서 1의 개수 세기

요즘은 그런 일이 잘 없지만 예전에는 프로그램을 짜면서 bit operation을 잘 써야하는 경우가 있었다. bit operation을 쓰는 이야라하면 bit operation이 대부분 가벼운 명령어로 + 정도의 로드를 가졌기 때문에 속도가 빨랐랐고, 컴퓨터가 bit를 기반으로 하기 때문에 코드 좀 더 깜끔하게 짤 수 있었다. 가끔 메모리가 부족할 때면 1byte 변수하나를 8개의 bit로 나눠 쓰려는 목적으로 사용하기도 했다.
요즘에야 컴퓨터도 좋아지고 자원이 넉넉해져서 효율적인 측면 보다는 프로그램의 구조적인 측면을 더 중요하게 보는 경향이 있어서 bit operation을 굳이 쓰지 않아도 되기 때문에 크게 쓸 일은 없지만 컴퓨터 아키텍쳐상 bit operation은 여전히 cpu 기본 operation이라서 2,8,16진수를 다룰 때 쓰면 찰떡 궁합으로 유용하게 쓸 수 있다.

그래서 그런 테크닉 중 재미있는 것이 있어서 소개하려고 한다.

c로 프로그램을 짜고 있다고 하자.
어떤 정수 n을 받아서 2진수로 나타내었을 때 1의 개수를 찾는 로직을 짜보자.
대부분의 사람들은 아마도 아래와 같이 실제로 2진수를 구할 것이다.

int count_org(int n) {
    int cnt;
    cnt=0;
    while(n!=0) {
        cnt+=n%2;
        n/=2;
    }
    return cnt;
}

하지만 이 보다 더 효율적이면서도 깔끔한 방법이 있다.

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

n과 (n-1)을 서로 and 연산을 하면 LSB와 가장 가까운 1만 없어지게 된다. 이 성질을 이용해서 0이 될 때까지 반복을 하고, 그 횟수를 카운팅 한다.

worst case time complexity는 동일하지만, 정확히 수에 존재하는 1의 개수 만큼의 step에 1의 개수를 구할 수 있다. bit operation을 잘 이용하면 위와 같이 좀 더 효율적이면서도 간단한 코드를 짤 수 있다. 이런 것을 응용하면 더 강력한 여러가지 연산을 조합해낼 수 있다.