# 바이너리에서 1인 Bit만 세어보기: Hamming weight(Population count algorithm)


2진수로 바꾸었을때 길이가 n인 정수에서 1인 bit만 세어보는 알고리즘을

발전하는 순서로 나열해 보았습니다.



1. 2로 계속 나누면서 나머지 세기 = O(n)

// 

public static int bitCount1(int i) {
int count = 0;

while (i > 0) {
count += i%2;
i /= 2;
}

return count;
}



2. bit shift 이용해서 1자리 세기 = O(n)

//

public static int bitCount2(int i) {
int count = 0;

while (i> 0) {
count += 0x1 & i;
i = i >> 1;
}

return count;
}



3-1. Population count 알고리즘으로 풀기 = O(log(n))

 // Java의 음수의 경우는 >> 할 때 맨 왼쪽에 1이 의도치않게 붙어서 >>> 를 사용하는게 낫다.

public static int bitCount3(int i) {
i = (i & 0x55555555) + ((i >>> 1) & 0x55555555); // ...01010101010101010101010101010101...
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333); // ...00110011001100110011001100110011...
i = (i & 0x0f0f0f0f) + ((i >>> 4) & 0x0f0f0f0f); // ...00001111000011110000111100001111...
i = (i & 0x00ff00ff) + ((i >>> 8) & 0x00ff00ff); // ...00000000111111110000000011111111...
i = (i & 0x0000ffff) + ((i >>> 16) & 0x0000ffff); // ...00000000000000001111111111111111...
return i & 0x3f;
}



3-2. 고민말고 Integer.bitCount() 쓰기 = O(log(n))

// 원리는 3-1과 똑같다.

public static int bitCount4(int i) {
return Integer.bitCount(i);
}



# 1~3 까지의 성능비교

// shift도 빠르지만...

for (int i=0; i < Integer.MAX_VALUE; i++) {
int a = bitCount(i);
}

bitCount1 = 90,453ms

bitCount2 = 31,677ms

bitCount3 = 3ms

bitCount4 = 3ms



4. Hardware 찬스 쓰기

CPU 영역에서 bit를 한번에 세주는 기능이 있다고 한다.




Reference:

- https://en.wikipedia.org/wiki/Hamming_weight

- https://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer

'Algorithms' 카테고리의 다른 글

Wildcard('?', '*') 패턴 매칭 알고리즘  (0) 2018.11.20

+ Recent posts