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