[면접 문제] 1로 설정된 비트의 수를 반환하는 함수 작성

문제: 주어진 정수를 컴퓨터에서 내부적으로 표현할 때 1로 설정된 비트의 수를 반환하는 함수를 작성하라.

방법1. 이진 문자열로 바꾸어 1인 문자를 센다.

친구에게 문제를 내보니 십진법을 이진법으로 변환하여 1의 갯수를 세려고 하고 있었다.

코드로 짠다면 아래와 같은 형태가 될 것이다. (여기서 숫자를 이진 문자열로 바꾸는 것은 Integer 클래스의 toBinaryString유틸리를 이용했다. 면접 같았으면 이것을 직접짰어야 했을 것이다.)

public static int countBit0(int value) {

        String strValue = Integer.toBinaryString(value);

        int count = 0;

        for (int i=0; i<strValue.length(); i++) {

               if (strValue.charAt(i) == '1') {

                       count++;

                }

        }

        return count;

}

하지만 생각해보면, 컴퓨터는 이미 내부적으로 숫자를 2의 보수 표현법으로 저장을 한다. 따라사 진법 변환으로 푸는 것은 불필요하게 연산을 해야하는 방법인 셈이 된다.

방법2. 비트연산자로 마스킹하여 센다.

보통 언어에서는 비트연산자를 지원한다. 특정 자리의 비트 값을 1과 AND 연산을 하면 그 값을 구할 수 있다.

주의 사항은 자바에서 >>를 쓰게 되면 음수의 경우 왼쪽의 비트가 1로 채워진다는 것이다. 무한 루프에 빠질 수 있다. 따라서  >>>를 사용하여 0으로 채워지게 해야 한다.

public static int countBit(int value) {

        int count = 0;

        while (value != 0) {

               count += (value & 1);

               value = value >>> 1;

        }

        return count;

}

방법3. 1을 빼서 구한 후 원래 수와 AND연산의 횟수로 구하기

비트 연산의 신(神)이라면 어떤 수에서 1을 빼면 내림 수 아래의 모든 비트가 뒤집힘을 알 것이다.

예를 들면 11000에서 1을 빼면 10111이 되어버린다. 처음 수에서 그 수를 1 뺀수를 AND 연산을 해보자.

11000 & (11000 - 1) = 11000 & 10111 = 10000

제일 오른쪽에 있는 1이 사라짐을 알 수 있다.

이 작업을 계속 반복하면 언젠가는 0이 된다. 즉, 반복한 횟수가 1의 개수이다.

자바 코드로 옮겨보면 아래와 같다.

public static int countBit(int value) {

        int count = 0;

        while (value != 0) {

               value = value & (value - 1);

               count++;

        }

        return count;

}

방법4. JVM의 구현

사실 자바에서는 언어 차원에서 비트의 수를 구하는 유틸리티 메서드가 있다.이름은 bitCount이다.

여기서 구현한 코드는 단순히 12개의 연산으로 비트의 수를 구한다. Integer.bitCount 랑 Long.bitCount 모두 구현되어 있다.

여기서 구현한 알고리즘은 해밍 가중치(Hamming weight) 또는 popcount, the sideways sum등으로 불린다. (링크)

마스크를 하는 패턴을 보면

 0x55555555는 이진수로 01010101010101010101010101010101이다. (1개는 0, 1개는 1...)

 0x33333333는 이진수로 00110011001100110011001100110011이다. (2개는 0, 2개는 1...)

 0x0f0f0f0f는 이진수로 00001111000011110000111100001111이다. (4개는 0, 4개는 1...)

 0x00ff00ff는 이진수로 00000000111111110000000011111111이다. (8개는 0, 8개는 1...)

 0x0000ffff는 이진수로 00000000000000001111111111111111이다. (16개는 0, 16개는 1...)

비트의 있는 카운터의 개수를 반씩 줄여나가면서 세는 알고리즘이다. 자세한 설명은 stackoverflow에 있으니 생략한다.(영어)

16비트로 예를 들면 아래와 같은 트리를 그릴 수 있다.

마치 이진 트리를 뒤집어 놓은 모습이다. 결국 이 알고리즘은 분할&정복(Divide and Conquer)을 하는 방법이다. (링크1,링크2)

public static int bitCount(int i) {

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

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

        i = (i + (i >>> 4)) & 0x0f0f0f0f;

        i = i + (i >>> 8);

        i = i + (i >>> 16);

        return i & 0x3f;

}

방법5. 하드웨어 명령을 이용

방법1~4까지는 프로그램을 통한 소프트웨어적인 방법이었다. CPU의 명령으로 한 번에 할 수 있다면 이것만큼 빠른 방법은 없을 것이다. 요즘 나오는 프로세서에서는 통한 한 명령으로 바로 개수 세기(population count)를 처리할 수 있는 하트웨어 기능을 제공한다.

GNU 컴파일러(예. gcc)에서는 __builtin_popcount() 를,

마이크로소프트 Visual Studio에서는 __popcnt()를 이용하면 된다.

아래의 코드는 Visual Studio 2008에서 돌려본 코드이다.

#include <stdio.h>

#include <intrin.h>

int countBits(int value) {

return __popcnt(value);

}

int main(int argc, char* argv[])

{

printf("count: %d\n", countBits(3));

return 0;

}

위의 코드를 디스어셈블리 해보면 아래와 같다. popcnt라는 명령을 호출함을 알 수 있다.

여러가지 카운트 세는 방법을 정리해보았는데, 실제 면접에서는 방법2 정도면 무난할 것으로 보인다.