// 망한글이니 댓글 참고바랍니다 ^.ㅠ
알고리즘 공부를 하고 있는데
빠르다 빠르다 소리만 들었지
비트연산자가 이 정도로 압도적인줄은 몰랐습니다.
프로그래머 게시판엔 고수분들이 대다수인건 알고 있지만
저와 같이 초보인 분들도 계실 거 같아 글을 올려봅니다.
아래 예시로 체감해보시면 될 것 같습니다.
====================================================================
주어진 문제는 두 양의 정수가 주어졌을 때 비트변화수의 총합을 구하는 문제입니다.
예를들어 10, 14가 있다고하면
10 = 1010
11 = 1011 → 1
12 = 1100 → 3
13 = 1101 → 1
14 = 1110 → 2
1 + 3 + 1 + 2 = 7 // 7이 비트변화의 총 합이 됩니다.
머릿속에 떠오르는 알고리즘이 있으신가요?
무대포로 일일이 이진수로 변경해서 해도 되지만
여기엔 하나의 규칙이 숨어있는데
각 비트의 자리수 값으로 나누어 떨어지면 그 비트는 변화한 것으로 볼 수 있습니다.
ex) 3 → 4 비트변화 시
4는 1, 2, 4로 나누어 떨어집니다. 고로 비트변화는 3이 됩니다.
4 → 5 비트변화 시
5는 1, 2, 4 중 1로만 나누어 떨어집니다. 고로 비트변화는 1이 됩니다.
15 → 16 비트변화 시
16은 1, 2, 4, 8, 16으로 나누어 떨어집니다. 고로 비트변화는 5가 됩니다.
감이 오시나요?
이제 위 규칙을 코드로 작성해본다면
/////////////////////////////////////////////
unsigned count_diff_2(unsigned x)
{
int count = 1;
int p = 1;
if (x <= 0)
return 0;
while (1)
{
int div = (int)pow((double)2, p);
if (x < div)
break;
if ((x % div) == 0)
count++;
p++;
}
return count;
}
/////////////////////////////////////////////
10, 14 의 비트변화를 계산한다고 가정하면
위 함수에는 11, 12, 13, 14가 들어가 일일이 계산되어 카운팅이 됩니다.
그럼 위의 함수를 가지고 프로그램을 돌리게 된다면 어느정도의 시간이 걸릴까요?
아래 사진에서 확인해보시죠
첫 번째, 두 번째에 있는 수가 시작 수와 끝 수이고 세 번째에 있는 값이 비트변화 수 입니다.
수행시간을 보니...
띠용?
1125초 = 18분 45초가 걸렸네요
물론 2~129까진 금방 계산했겠지만
맨 마지막 값... 2억부터 10억까지 비트변화수를 계산하는건 만만치 않은 일입니다.
비트변화수가 16억6천만...
그런데 여기 또 다른 함수가 있습니다
이 함수는 위에서 봤던 함수와 똑같은 원리지만
비트연산자로 작성되어있는 코드입니다.
///////////////////////////////////////////
unsigned count_diff_1(unsigned x)
{
unsigned n = 0;
x ^= x - 1;
while (x) {
if (x & 1) n++;
x >>= 1;
}
return n;
}
/////////////////////////////////////////////
원리는 똑같습니다.
아까와 같이 10, 14의 값을 구한다면
11, 12, 13, 14가 들어가게 되고
11이 들어가면 10과 XOR 연산을 하여
그 중 1인 비트값만 찾는겁니다.
원리는 똑같고 다른게 없습니다.
그런데 띠용???
아래 사진을 보세요...
........?????
17초가 걸렸습니다....
17초.....
1125초..... 17초.....
무려 66배의 차이입니다.
체감이 되시나요....
이 문제 덕에
실무에 나가있지 않아 자세히는 모르지만
아무리 컴퓨터 성능이 좋아졌다고 한들
옛날처럼 작은 데이터가 아닌 빅데이터를 다루는 시대에서
알고리즘 구성이 중요하다고 생각하게 되었습니다.
이 문제를 보고 뼈저느리게 느꼈구요ㄷㄷ
그냥 충격먹어서 써본 글입니다...
아직도 신기하네요
비트연산자 만만세
베스트예감
