요즘 새로운 알고리즘 스터디를 시작했습니다.
바로 달레의 코드 유튜브 채널(과 여러 블로그 등)을 운영하시는 달레님의 리트코드 스터디입니다.
해외 취업을 준비하시는분들이나, 리트코드를 통해 알고리즘을 공부하실 분들께서 관심이 있으시다면 참고하시면 좋을 것 같습니다.
스터디 첫 주차에는 191. Number of 1 Bits 문제를 풀었습니다.
easy 등급 문제라 어렵지는 않았지만, bitCount 함수를 발견한 후 그 원리를 이해해보고 싶었습니다.
정확한 발단을 좀 더 말씀드리자면, 제 풀이는 분명 O(logn)의 시간복잡도를 가졌고 나름 깔끔하게 잘 풀었다고 생각했었습니다.
function hammingWeight(n: number): number {
// 시간복잡도: O(logn)
// 공간복잡도: O(logn)
// 가독성이 좋고, 공간복잡도가 그리 나쁘지 않다.
return n.toString(2).split('1').length - 1;
// 시간복잡도: O(logn)
// 공간복잡도: O(1)
// 성능이 더 좋지만, 비트연산자가 낯선 사람들에게는 이해하기 어려울 수 있다.
let count = 0;
while (n !== 0) {
count += n & 1;
n >>>= 1;
}
return count;
}그런데, Java 사용자분께서 내장함수 단 한 줄로 O(1) 풀이를 하셨더라구요.
풀이는 아래와 같습니다.
// 시간복잡도 O(1)
// 공간복잡도 O(1)
class Solution {
public int hammingWeight(int n) {
return Integer.bitCount(n);
}
}?? 아니 이게 어떻게 되는거지? 말이 되나?
이런 생각이 들어서 찾아보니, Integer.bitCount라는 함수의 내부 구현은 이렇더라구요.
public final class Integer
{
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;
}
}그래서 이 함수를 (잘 이해는 안되지만) 아래와 같이 구현해서 제출해보니 역시나 O(1)의 시간복잡도로 당연히 통과되었습니다.
function hammingWeight(i: number): number {
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;
};자 그러면, 이 함수가 어떻게 동작하는지 이해해보도록 하겠습니다.
비트연산자
먼저, 이 함수는 비트연산자를 사용하고 있습니다.
비트연산자는 이미 잘 알려져 있긴 하지만, 다시 한 번 간단히 설명드리겠습니다.
&: 비트 AND 연산자>>>: 부호없는 우측 시프트 연산자
이 두 연산자에 대해 간단히 설명하자면, &는 두 비트가 모두 1일 때만 1을 반환하고, >>>는 부호비트를 무시하고 오른쪽으로 비트를 이동시킵니다.
예를 들자면, 5(101)와 3(011)의 & 연산은 1(001)이 되고, 5(101)의 >>> 1은 2(010)이 됩니다.
101 = 5
011 = 3
& ---
001 = 1 101 = 5
>>> 1
010 = 2비트연산자를 이용한 비트 카운팅
자, 다시 한번 이전의 함수를 가져와보겠습니다.
function hammingWeight(i: number): number {
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단계로 이루어져 있는데요, 한 단계씩 차근차근 알아보겠습니다.
우선은 만만한 숫자를 뽑아 i = 42로 예를 들어보겠습니다.
42 = 0000 0000 0000 0000 0000 0000 0010 10101단계 - 2비트씩 묶어서 1로 만들기
i = i - ((i >>> 1) & 0x55555555);
이 코드를 보면 i를 오른쪽으로 1비트씩 시프트한 값과 0x55555555를 & 연산한 값을 빼는 것을 볼 수 있습니다.
피상적으로는 알겠는데, 이게 무슨 의미일까요?
우선은 잘 모르겠으니, 한번 직접 계산해 보겠습니다.
먼저 0x55555555는 16진수로, 2진수로 표현하면 0101 0101 0101 0101 0101 0101 0101 0101입니다.
0000 0000 0000 0000 0000 0000 0001 0101 = 42 >>> 1 = 21
& 0101 0101 0101 0101 0101 0101 0101 0101
-------------------------------------------
0000 0000 0000 0000 0000 0000 0001 0101 = 21 & 0x55555555 = 21 0000 0000 0000 0000 0000 0000 0010 1010 = 42
- 0000 0000 0000 0000 0000 0000 0001 0101 = 21
-------------------------------------------
0000 0000 0000 0000 0000 0000 0001 0101 = 21자 이렇게 계산하면 결과는 i = 21이 됩니다.
이렇게 2비트씩 묶어서 1로 만드는 이유는 무엇일까요?
아직은 잘 모르겠고 와닿지 않습니다. 음.. 좀 더 알아봐야겠습니다.
2단계 - 4비트씩 묶어서 1로 만들기
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
이 코드는 i와 i를 오른쪽으로 2비트씩 시프트한 값을 0x33333333와 각각 &연산한 값을 더하는 것을 볼 수 있습니다.
이번에는 마스킹을 두 번이나 하고 있습니다.
이게 대체 무슨 의미일까요? 마스킹하는 숫자의 형태를 보면 뭔가 규칙은 있는 것 같은데..?
우선은 계속 계산해보겠습니다.
0x33333333는 2진수로 표현하면 0011 0011 0011 0011 0011 0011 0011 0011입니다.
0000 0000 0000 0000 0000 0000 0001 0101 = 21
& 0011 0011 0011 0011 0011 0011 0011 0011
-------------------------------------------
0000 0000 0000 0000 0000 0000 0001 0001 = 17 0000 0000 0000 0000 0000 0000 0001 0101 = 21
>>> 2
0000 0000 0000 0000 0000 0000 0000 0101 = 5
& 0011 0011 0011 0011 0011 0011 0011 0011
-------------------------------------------
0000 0000 0000 0000 0000 0000 0000 0001 = 1 0000 0000 0000 0000 0000 0000 0001 0001 = 17
+ 0000 0000 0000 0000 0000 0000 0000 0001 = 1
-------------------------------------------
0000 0000 0000 0000 0000 0000 0001 0010 = 18이렇게 계산하면 i = 18이 됩니다. 이렇게 4비트씩 묶어서 1로 만드는 이유는 무엇일까요?
글쎼요.. 여전히 잘 와닿지가 않는 것 같습니다... 무슨 근거로 이렇게 계산하는걸까요?
3단계 - 8비트씩 묶어서 1로 만들기
i = (i + (i >>> 4)) & 0x0f0f0f0f;
이번에는 i와 i를 오른쪽으로 4비트씩 시프트한 값을 더하고, 0x0f0f0f0f와 & 연산(마스킹)한 값을 i에 대입하고 있습니다.
이게 뭘 의미하는지는 점점 모르겠네요.
게다가 방금 전에는 두 번 진행한 마스킹을 이번에는 한 번만 적용했네요.
그렇지만 여전히, 마스크의 형태를 보면 뭔가 분명히 의미는 있는것 같죠?
0x0f0f0f0f는 2진수로 표현하면 0000 1111 0000 1111 0000 1111 0000 1111입니다.
0000 0000 0000 0000 0000 0000 0001 0010 = 18
>>> 4
0000 0000 0000 0000 0000 0000 0000 0001 = 1
+ 0000 0000 0000 0000 0000 0000 0001 0010 = 18
-------------------------------------------
0000 0000 0000 0000 0000 0000 0001 0011 = 19 0000 0000 0000 0000 0000 0000 0001 0011 = 19
& 0000 1111 0000 1111 0000 1111 0000 1111
-------------------------------------------
0000 0000 0000 0000 0000 0000 0000 0011 = 3자, 이렇게 계산하면 i = 3이 됩니다.
뭔가 진행이 되고는 있는 것 같은데, 아직까지도 갈피를 못잡겠습니다.
이렇게 8비트씩 묶어서 1로 만드는 이유는 무엇일까요?
전개되는 모양을 보면 분명히 뭔가 규칙이 있을 것 같은데, 아직까지도 잘 모르겠습니다.
4단계 - 16비트씩 묶어서 1로 만들기
i = i + (i >>> 8);
4단계에서는 i와 i를 오른쪽으로 8비트씩 시프트한 값을 더하는 것을 볼 수 있습니다.
이번에는 다시 마스킹을 하지 않았습니다. 엥..? 대체 무슨 규칙이 있는걸까요?
0000 0000 0000 0000 0000 0000 0000 0011 = 3
>>> 8
0000 0000 0000 0000 0000 0000 0000 0000 = 0
+ 0000 0000 0000 0000 0000 0000 0000 0011 = 3
-------------------------------------------
0000 0000 0000 0000 0000 0000 0000 0011 = 3이렇게 계산하면 그대로 i = 3이 됩니다.
분명 뭔가 규칙이 있을 것 같은데, 아직까지도 정확히 파악은 되지 않습니다.
5단계 - 32비트씩 묶어서 1로 만들기
i = i + (i >>> 16);
5단계에서는 i와 i를 오른쪽으로 16비트씩 시프트한 값을 더하는 것을 볼 수 있습니다.
이번에도 별도의 마스킹은 없습니다.
0000 0000 0000 0000 0000 0000 0000 0011 = 3
>>> 16
0000 0000 0000 0000 0000 0000 0000 0000 = 0
+ 0000 0000 0000 0000 0000 0000 0000 0011 = 3
-------------------------------------------
0000 0000 0000 0000 0000 0000 0000 0011 = 3마지막 계산
이렇게 5단계를 거치면 i = 3이 되고, 마지막으로 i & 0x3f를 하면 3 & 0x3f = 3이 됩니다.
다만 여기서 0x3f는 2진수로 표현하면 0000 0000 0000 0000 0000 0000 0011 1111이고, 마지막 6비트만 남기는 것을 볼 수 있습니다.
6비트이면 0부터 63까지 표현이 가능할텐데, 이게 무슨 의미일까요?
0000 0000 0000 0000 0000 0000 0000 0011 = 3
& 0000 0000 0000 0000 0000 0000 0011 1111 = 0x3f
-------------------------------------------
0000 0000 0000 0000 0000 0000 0000 0011 = 3오.. 아직 정확히는 모르겠지만 어느새 정답인 3이 나와있네요.
아직 정확히는 모르겠지만 Integer.bitCount 함수가 어찌저찌 동작은 한다는 결과를 얻었습니다.
저도 처음엔 '엥..?' 하면서 한번에 이해가 잘 되지 않았는데요, 이해가 되면서는 정말 신기한 함수라고 생각이 들었습니다.
이제는 정말로 하나씩, 자세히 알아보겠습니다.
좀 더 확실한 이해를 위해
좀 더 확실한 이해를 위해, i = 42가 아닌, 32비트의 최대값인 i = 0xffffffff를 가지고 계산해보겠습니다.
1단계 - 2비트씩 묶어서 1로 만들기
i = i - ((i >>> 1) & 0x55555555);
1111 1111 1111 1111 1111 1111 1111 1111 = 0xffffffff
>>> 1
0111 1111 1111 1111 1111 1111 1111 1111 = 0x7fffffff
& 0101 0101 0101 0101 0101 0101 0101 0101 = 0x55555555
-------------------------------------------
0101 0101 0101 0101 0101 0101 0101 0101 = 0x55555555 1111 1111 1111 1111 1111 1111 1111 1111 = 0xffffffff
- 0101 0101 0101 0101 0101 0101 0101 0101 = 0x55555555
-------------------------------------------
1010 1010 1010 1010 1010 1010 1010 1010 = 0xaaaaaaaa위의 1단계의 목적은 각 2비트 내에서 1의 개수를 세는것이었습니다.
그리고 오른쪽으로 1비트씩 시프트한 수를 0x55555555로 마스킹하는 것은 각각의 2비트 내에서 상위 1비트의 값들을 얻기 위함입니다.
각각의 2비트를 11, 10, 01, 00로 예를 들어보겠습니다. 이 경우 각각 2비트 내에서 1의 개수는 2, 1, 1, 0개 입니다.
그리고 이를 오른쪽으로 1비트씩 시프트한 수를 0x55555555로 마스킹하면 각각 01, 01, 00, 00이 되며, 이를 원래 수에서 빼면 각각 10, 01, 01, 00이 됩니다.
즉, 3, 2, 1, 0에서 결과값인 2, 1, 1, 0을 얻을 수 있습니다.
| 2비트 | 2비트(10진수) | 상위 1비트 | 상위 1비트(10진수) | 차이 | 새로운 2비트 |
|---|---|---|---|---|---|
| 11 | 3 | 1 | 1 | 2 | 10 |
| 10 | 2 | 1 | 1 | 1 | 01 |
| 01 | 1 | 0 | 0 | 1 | 01 |
| 00 | 0 | 0 | 0 | 0 | 00 |
결과적으로 각각의 2비트 내에 있는 1의 개수를 2비트의 2진수로 압축하게 됩니다.
즉, 1111 1111 1111 1111 1111 1111 1111 1111가 1010 1010 1010 1010 1010 1010 1010 1010으로 변환됩니다.
이 단계에서 i라는 변수의 10진수로서의 의미는 사라지고, 각각의 2비트 내에서 1의 개수를 2비트의 2진수로 압축하는 것이 목적입니다.
2단계 - 4비트씩 묶어서 1로 만들기
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
1010 1010 1010 1010 1010 1010 1010 1010 = 0xaaaaaaaa
& 0011 0011 0011 0011 0011 0011 0011 0011 = 0x33333333
-------------------------------------------
0010 0010 0010 0010 0010 0010 0010 0010 = 0x22222222 1010 1010 1010 1010 1010 1010 1010 1010 = 0xaaaaaaaa
>>> 2
0010 1010 1010 1010 1010 1010 1010 1010 = 0x2aaaaaaa
& 0011 0011 0011 0011 0011 0011 0011 0011 = 0x33333333
-------------------------------------------
0010 0010 0010 0010 0010 0010 0010 0010 = 0x22222222 0010 0010 0010 0010 0010 0010 0010 0010 = 0x22222222
+ 0010 0010 0010 0010 0010 0010 0010 0010 = 0x22222222
-------------------------------------------
0100 0100 0100 0100 0100 0100 0100 0100 = 0x44444444여기서도 위와 비슷하지만, 이번에는 4비트(0000) 내에서 1의 개수를 세기 위함입니다.
0x33333333과 마스킹하면 각각의 4비트 내에서 하위 2비트의 값이 얻어집니다.
그리고 오른쪽으로 2비트씩 시프트한 수를 0x33333333로 마스킹하면 각각의 4비트 내에서 상위 2비트의 값이 얻어집니다.
| 4비트 | 상위 2비트(10진수) | 하위 2비트(10진수) | 합계 | 새로운 4비트 |
|---|---|---|---|---|
| 10 10 | 2 | 2 | 4 | 0100 |
| 01 10 | 1 | 2 | 4 | 0011 |
| 00 10 | 0 | 2 | 4 | 0010 |
| 00 01 | 0 | 1 | 2 | 0001 |
예를 들어, 1010, 0110, 0010, 0001의 경우 각각 상위, 하위 비트로 나누어 0x33333333과 마스킹하면 각각 상위는 10, 01, 00, 00, 하위는 10, 10, 10, 01이 됩니다.
눈썰미가 좋은 분들은 이미 캐치하셨을텐데, 여기서 중요한점은 이전 계산 결과에 따라 각각의 상하위 비트의 값이 ['10', '01', '01', '00']밖에 될 수 없다는 점입니다.
네, 맞습니다. 당연하게도 2비트에서 1의 개수는 2보다 작거나 같아야 하기 때문이죠.
위의 예시 숫자들은 10진수로 각각 2, 1, 0, 0(상위 비트)과 2, 2, 2, 1(하위 비트)이 되고 이를 더하면 각각 4, 3, 2, 1이 됩니다. 이 단계의 목표인 4비트 2진수로는 0100, 0011, 0010, 0001이 되는 것입니다.
1010, 0110, 0010, 0001에 대해 결론을 10진법으로 예로 들어보자면, 두 개씩의 숫자로 이루어진 22, 12, 02, 01을 각각 0100, 0011, 0010, 0010, 즉 4, 3, 2, 1로 압축하 것입니다.
| 2비트 2진수 | 4비트 2진수 | 10진수 |
|---|---|---|
| 10 10 | 0100 | 4 |
| 01 10 | 0011 | 3 |
| 00 10 | 0010 | 2 |
| 00 01 | 0010 | 1 |
3단계 - 8비트씩 묶어서 1로 만들기
i = (i + (i >>> 4)) & 0x0f0f0f0f;
0100 0100 0100 0100 0100 0100 0100 0100 = 0x44444444
>>> 4
0000 0100 0100 0100 0100 0100 0100 0100 = 0x04444444
+ 0100 0100 0100 0100 0100 0100 0100 0100 = 0x44444444
-------------------------------------------
0100 1000 1000 1000 1000 1000 1000 1000 = 0x48888888 0100 1000 1000 1000 1000 1000 1000 1000 = 0x48888888
& 0000 1111 0000 1111 0000 1111 0000 1111 = 0x0f0f0f0f
-------------------------------------------
0000 1000 0000 1000 0000 1000 0000 1000 = 0x08080808이제 어느정도 이해가 되시나요?
이번 단계에서는 8비트 내에서 1의 개수를 세기 위함입니다.
매번 i를 계산하는 방식이 조금씩 다르지만, 결국엔 1의 개수를 세는 것이 목적입니다.
이번에는 i와 i >>> 4를 더하고, 0x0f0f0f0f로 마스킹한 값을 구하는데, 이또한 위와 같은 방식으로 앞쪽 4비트가 의미하는 10진수와 뒤쪽 4비트가 의미하는 10진수를 더하는 것입니다.
표로 정리하면 아래와 같겠죠.
다만 여기서도 가능한 숫자는 최대 0100일겁니다.
왜냐하면 4비트 내에서 1의 개수는 4보다 작거나 같아야 하기 때문이죠.
| 4비트 2진수 | 8비트 2진수 | 10진수 |
|---|---|---|
| 0100 0011 | 0000 0111 | 7 |
| 0011 0010 | 0000 0101 | 5 |
자, 이제 확실히 감이 잡히실거라 생각합니다.
4단계 - 16비트씩 묶어서 1로 만들기
i = i + (i >>> 8);
0000 1000 0000 1000 0000 1000 0000 1000 = 0x08080808
>>> 8
0000 0000 0000 1000 0000 1000 0000 1000 = 0x00080808
+ 0000 1000 0000 1000 0000 1000 0000 1000 = 0x08080808
-------------------------------------------
0000 1000 0001 0000 0001 0000 0001 0000 = 0x08101010이번에는 16비트 내에서 1의 개수를 세기 위함입니다.
여전하게도 앞뒤 각각 8비트의 최대는 0000 1000이겠죠? 왜냐하면 8비트 내에서 1의 개수이니까요.
그렇다보니 이제는 별도로 마스킹을 할 이유도 없게 되었네요.
| 8비트 2진수 | 16비트 2진수 | 10진수 |
|---|---|---|
| 0000 1000 0000 1000 | 0000 0000 0001 0000 | 16 |
| 0000 0100 0000 1000 | 0000 0000 0000 1100 | 12 |
하지만 마스킹이 없으니 약간의 부작용이 있습니다.
위의 결과처럼 앞, 뒤 16비트의 결과가 0000 1000 0001 0000로 나오는데, 이는 10진수로 2064이 나오게 됩니다. 이전까지의 결과대로라면 0000 0000 0001 0000로 16이 나와야 하는데 말이죠.
뭐, 결과적으로는 무시될 부분이니, 조심해서 넘어가도록 하겠습니다.
5단계 - 32비트씩 묶어서 1로 만들기
i = i + (i >>> 16);
0000 1000 0001 0000 0001 0000 0001 0000 = 0x08101010
>>> 16
0000 0000 0000 0000 0000 1000 0001 0000 = 0x00000810
+ 0000 1000 0001 0000 0001 0000 0001 0000 = 0x08101010
-------------------------------------------
0000 1000 0001 0000 0001 1000 0010 0000 = 0x08101820자 이제 거의 끝났습니다.
이번에는 32비트 내에서 1의 개수를 세기 위함입니다.
역시나 앞, 뒤 각각 16비트의 최대값은 0000 1000 0001 0000가 나오고, 위에서 말했듯 여기서 2048은 무시하고 16만 신경쓰면 됩니다.
마지막 계산
i & 0x3f
0000 1000 0001 0000 0001 1000 0010 0000 = 0x08101820
& 0000 0000 0000 0000 0000 0011 1111 1111 = 0x000003ff
-------------------------------------------
0000 0000 0000 0000 0000 0000 0010 0000 = 0x00000020네, 방금 전 4~5단계에서 계산한 결과에서, 우리에게 필요한 하위 6비트만을 마스킹한 결과가 나왔습니다.
이 과정에서 이전에 신경 쓸 필요 없다고 말씀드린 앞부분의 불필요한 숫자는 모두 무시되는것을 확인하실 수 있습니다.
이렇게 계산하면 i = 0000 0000 0000 0000 0000 0000 0010 0000 = 0x 0000 0020이 됩니다. 그리고 이는 10진수로 32가 되죠.
이렇게 Integer.bitCount 함수가 동작하는 방식을 한번 직접 보았습니다.
마치며
정리가 조금 부족하고, 2진수와 10진수를 번갈아가며 설명하다보니 다소 혼란스러우실 수 있을 것 같습니다. 그래도 조금이나마 이해에 도움이 되셨으면 좋겠습니다.
혹시 틀린 부분이나, 설명이 납득이 안되는 부분이 있으시면 언제든지 피드백 주시면 감사하겠습니다!
