게시판 즐겨찾기
편집
드래그 앤 드롭으로
즐겨찾기 아이콘 위치 수정이 가능합니다.
[C] 비트연산자 속도 체감
게시물ID : humorbest_1515120짧은주소 복사하기
작성자 : 전벙글이예요
추천 : 43
조회수 : 7594회
댓글수 : 28개
베스트 등록시간 : 2017/11/01 17:19:17
원본글 작성시간 : 2017/10/31 22:49:18
// 망한글이니 댓글 참고바랍니다 ^.ㅠ

알고리즘 공부를 하고 있는데

빠르다 빠르다 소리만 들었지

비트연산자가 이 정도로 압도적인줄은 몰랐습니다.

프로그래머 게시판엔 고수분들이 대다수인건 알고 있지만

저와 같이 초보인 분들도 계실 거 같아 글을 올려봅니다.

아래 예시로 체감해보시면 될 것 같습니다.

====================================================================

주어진 문제는 두 양의 정수가 주어졌을 때 비트변화수의 총합을 구하는 문제입니다.

예를들어 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이 됩니다.

→ 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가 들어가 일일이 계산되어 카운팅이 됩니다.

그럼 위의 함수를 가지고 프로그램을 돌리게 된다면 어느정도의 시간이 걸릴까요?

아래 사진에서 확인해보시죠

2.png


첫 번째, 두 번째에 있는 수가 시작 수와 끝 수이고 세 번째에 있는 값이 비트변화 수 입니다.

수행시간을 보니...

띠용?

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인 비트값만 찾는겁니다.

원리는 똑같고 다른게 없습니다.

그런데 띠용???

아래 사진을 보세요...

1.png


........?????

17초가 걸렸습니다....

17초.....

1125초..... 17초.....

무려 66배의 차이입니다.

체감이 되시나요....

이 문제 덕에

실무에 나가있지 않아 자세히는 모르지만

아무리 컴퓨터 성능이 좋아졌다고 한들

옛날처럼 작은 데이터가 아닌 빅데이터를 다루는 시대에서

알고리즘 구성이 중요하다고 생각하게 되었습니다.

이 문제를 보고 뼈저느리게 느꼈구요ㄷㄷ

그냥 충격먹어서 써본 글입니다...

아직도 신기하네요

비트연산자 만만세


꼬릿말 보기
전체 추천리스트 보기
새로운 댓글이 없습니다.
새로운 댓글 확인하기
◀뒤로가기
PC버전
맨위로▲
공지 운영 자료창고 청소년보호