// 망한글이니 댓글 참고바랍니다 ^.ㅠ
알고리즘 공부를 하고 있는데
비트연산자가 이 정도로 압도적인줄은 몰랐습니다.
프로그래머 게시판엔 고수분들이 대다수인건 알고 있지만
저와 같이 초보인 분들도 계실 거 같아 글을 올려봅니다.
아래 예시로 체감해보시면 될 것 같습니다.
====================================================================
주어진 문제는 두 양의 정수가 주어졌을 때 비트변화수의 총합을 구하는 문제입니다.
예를들어 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 의 비트변화를 계산한다고 가정하면
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배의 차이입니다.
체감이 되시나요....
이 문제 덕에
실무에 나가있지 않아 자세히는 모르지만
아무리 컴퓨터 성능이 좋아졌다고 한들
옛날처럼 작은 데이터가 아닌 빅데이터를 다루는 시대에서
알고리즘 구성이 중요하다고 생각하게 되었습니다.
이 문제를 보고 뼈저느리게 느꼈구요ㄷㄷ
그냥 충격먹어서 써본 글입니다...
아직도 신기하네요
비트연산자 만만세
글쓰기