[ leetcode 문제풀이 ] Number of 1 Bits

https://leetcode.com/problems/number-of-1-bits

Number of 1 Bits - LeetCode

(Number of 1 Bits 문제는 위 링크에서 풀어보실 수 있습니다.)

 

 

< Number of 1 Bits 문제 설명 >

 

Number of 1 Bits 문제는 다음과 같다.

Write a function that takes an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weight).

부호가 없는 (32비트)정수를 입력받아 정수가 갖고 있는 1 비트의 갯수를 리턴하여라.

 

다음 세 가지 출력 예시가 주어졌다.

주어진 제한 조건은 input이 반드시 길이 32의 binary string이라는 것이고

Follow up question으로는 함수가 많은 횟수 실행되는 경우 어떻게 최적화 할 것인가? 이다.

 

 

---

< Number of 1 Bits 문제 접근 - 기본 >

 

길이 32의 binary string에서 1의 개수를 세는 가장 간단한 방법은 맨 앞 혹은 맨 뒤에서부터 하나하나 1이 있는지를 확인하는 방법이 있을 것이다. 이를 코드로 나타내면 아래와 같다. (Cpp 사용)

int hammingWeight(uint32_t n){
    int cnt = 0;				//비트 카운트 변수
    while(n){					//n에 대한 오른쪽 시프트에 의해 n이 0이 될 때까지 반복
    	cnt += n&1;				//맨 오른쪽 자리에 1이 있는경우 카운트 1 추가
        n >>= 1;
    }
    return cnt;
}

이 코드의 시간복잡도를 살펴보자면 while문의 반복이 시간복잡도를 결정함을 알 수 있고, while문의 반복 횟수는 n에 대한 시프트 연산의 횟수이다. n은 32비트 binary string으로 그 길이가 정해진 상수이므로 시간복잡도는 O(1)이다.

 

 

---

< Number of 1 Bits 문제 접근 - 심화 >

 

이번에는 bitwise operation을 적극 활용해서 hamming weight를 구하는 방법에 대해 알아보자.

 

이 방법에서는 이해하기 쉽게 filter을 이용해 1을 거른다고 생각하면 된다. 사용하는 filter는 

01010101 ... 0101, 00110011 ... 0011, 00001111 ... 1111, ...이런 식으로 반복되는 0과 1 배열로 구성된다.

 

input으로 16비트 정수 a = 0110110010111010 가 들어온 경우를 예로 들어 hamming weight를 구하는 과정을 아래 표를 통해 알아보자.

from Wikipedia

01010101 ... 0101 filter를 통한 연산을 살펴보면 b0는 a의 짝수 번째 1을 filtering하며 b1은 a의 홀수 번째 1을 filtering해 짝수 번째 자리로 (오른쪽으로 1칸) 시프트 한다. 이렇게 filtering해낸 b0와 b1을 합한 c는 2비트 조각에 들어가 있는 1의 개수를 나타낸다고 할 수 있다. 이와 같은 과정을 000000 .... 111111 filter까지 반복하여 주면 최종적으로 얻어지는 binary string은 전체 input에 대한 1의 개수가 되는 것이다.

 

이를 코드로 나타내면 아래와 같다. (Cpp 사용)

uint32_t m1 = 0x55555555;				// binary: 0101 ...
uint32_t m2 = 0x33333333;				// binary: 00110011 ...
uint32_t m4 = 0x0f0f0f0f;				// binary: 4 zeros, 4 ones ...
uint32_t m8 = 0x00ff00ff;				// binary: 8 zeros, 8 ones ...
uint32_t m16 = 0x0000ffff;				// binary: 16 zeros, 16 ones ...

int hammingWeight(uint32_t n) {
    n = (n & m1) + ((n >> 1) & m1);
    n = (n & m2) + ((n >> 2) & m2);
    n = (n & m4) + ((n >> 4) & m4);
    n = (n & m8) + ((n >> 8) & m8);
    n = (n & m16) + ((n >> 16) & m16);
    return n;
}

 이 코드의 시간복잡도는 O(1)이며, 더 정확하게 말하자면 총 20회의 산술 연산(shift, add, and)를 사용한다.

 

 

위 코드를 살짝 바꿔 최적화를 진행해보면 아래와 같이 쓸 수 있다.

int hammingWeight(uint32_t n) {
    n -= (n >> 1) & m1;				//각 조각에서 10 -> 01로, 01 -> 01로, 11 -> 10으로
    n = (n & m2) + ((n >> 2) & m2);
    n = (n + (n >> 4)) & m4;			// m4에 대한 AND 연산을 한 번에 처리
    n += n >> 8;				// 각 16비트 카운트를 뒷 8비트에 몰아넣기
    n += n >> 16;				// 각 32비트 카운트를 뒷 16비트에 몰아넣기
    return n & 0x3f;				//trash 값을 제거
}

각 줄이 어떻게 동작하는지 앞서 본 16비트 정수 a = 0110110010111010를 통해 살펴보자.

 

2번째 줄 : n = 0110110010111010

                  -0001010001010101    // (n >> 1) & m1임

                ->0101100001100101    // filter을 사용한 결과 c와 동일

3번째 줄 : n -> 0010001000110010  // filter 식과 동일

4번째 줄 : n = 0010001000110010

                 +0000001000100011    // n >> 4

                ->0000010000000101   // filter을 사용한 결과 g와 동일

5번째 줄 : n ->0000010000001001   // 밑줄 친 부분은 trash 값이 저장됨

(16비트 예시이기에 6번째 줄의 연산은 없음)

7번째 줄 : n = 0000010000001001 

                 &0000000000011111    // 16비트 정수이므로 hamming weight 최댓값은 16 = 10000.

                                                    따라서 0x1f와 AND연산을 통해 trash값 제거

                ->0000000000001001 = 9(ANSWER)

 

이제 위 코드가 어떻게 동작하는지, 제대로 동작은 하는지는 확인되었다.

 

 

한편, 위 코드는 알려진 다른 어떤 것보다 적은 산술 연산을 사용한다. (곱셈을 사용하지 않은 코드 중 가장 적은 산술 연산, 느린 곱셈을 사용하는 시스템에 구현함) 총 15회의 산술 연산을 사용한다. (shift, and, add, subtract)

 

그렇다면 코드의 각 줄이 어떻게 나온건지 생각해보자. 

 

2번째 줄의 경우 2비트에서 나올 수 있는 모든 경우(00, 01, 10, 11)에 대해 그 결과

00 -> 00  /  01 -> 01 / 10 -> 01  /  11 -> 10 가 filter을 이용한 결과와 동일하다.

3번째 줄과 4번째 줄의 경우...는 왜 두 케이스에 대해 다르게 구하는지 아직 모르겠다. 2번째 줄도 3번째 줄과 마찬가지로 AND연산을 한 번에 처리하면 안되는건가 싶다. (물론 그렇게 하면 잘못된 출력이 나오는 것까지는 확인했다.)

5~ 번째 줄의 코드를 trash 값을 생성하는 연산이라고 하자. 왜 5번째 이후 줄부터 이 연산을 사용하는 것일가?

32비트 수의 경우 hamming weight의 최댓값은 32 = 100000이므로 trash값을 생성하는 연산(shift후 더하기)은 나눈 조각의 크기가 6이상일 경우만 가능하다. 따라서 조각이 8이 되는 5번째 줄부터 적용됨을 알 수 있다. (먄약 input이 256비트라면 조각이 16이 되는 경우부터 적용될 것이다.)

 

(이 외에도 곱셈을 사용한 알고리즘이 Wikipedia/Hamming_weight에 있으니 궁금하면 찾아보는 것을 추천드립니다.)

 

 

 

입력으로 주어지는 binary string이 대부분 0으로 이루어져 있을 때 유용한 알고리즘도 있는데, 이를 코드로 나타내면 아래와 같다. (Cpp 사용)

int hammingWeight(uint32_t n) {
    int cnt;
    for(cnt=0; n; cnt++)
    	n &= n-1;			// n의 가장 오른쪽에 있는 1을 0으로 만드는 연산
    return cnt;
}

위 코드는 맨 처음에 한 비트씩 직접 1인지 확인하는 코드보다 더 빠르며, 특히 binary string이 대부분 0으로 이루어진 경우 그 차이는 극명하게 나타남을 알 수 있다.