|
저자가 카네기멜론 대학의 박사과정에 입학해서, 알고리즘 수업을 듣던 첫날, 존 벤틀리 교수 (Jon Bentley, Programming Pearl 의 저자, 국내에는 "생각하는 프로그래밍" 이란 책으로 번역. ) 가 학생들에서 이진검색을 구현해 보라고 시킨 후에 그중 몇명을 앞에 나와서 발표하라고 했을 때의 충격을 아직도 기억하고 있다고 쓰고 있다. 물론, 당연하게도 ^^, 대부분의 학생들이 구현한 이진검색은 버그가 있었다. 자, 이 코드의 어떤 부분에 버그가 있을까.. 정답은 아래 라인이다. 만약 low 와 high 가 충분히 큰 숫자라서 이 두수의 합이 integer 의 범위 ( 32 비트의 경우 2,147,483,648 ) 를 넘어서게 되면 결국 Overflow 가 발생하게 된다. 그래서 이 부분에서 mid 값을 배열 a 의 인덱스로 사용한 부분에서 배열의 잘못된 인덱스로 접근하게 되어 생기는 ArrayIndexOutOfBoundsException 에러가 나게 된다. * 주의사항 : 조수아 벤틀리는 원문에서 두 양수의 합이 Overflow 가 나는 경우 그 결과는 음수가 되어 배열의 인덱스를 음수로 접근하게 되어 ArrayIndexOutOfBoundsException 에러가 난다고 쓰고 있으나, 후에 덧글을 통해서 C99 스펙의 경우 signed integer 의 두 수의 overflow 의 경우 항상 음수가 되는 것은 아닌 undefined 가 된다고 수정하고 있다. 어쨌든 에러는 에러이다... ^^ ; 조수아 벤틀리는 이 라인을 아래와 같이 고치는 것이 좋겠다고 쓰고 있다. ( C / C++ 의 경우 ) 참고로 비트연산자 >> 1 은 /2 와 같다. >> 1 과 같이 비트연산으로 계산을 할 경우 /2 보다 조금 더 빠르다. ;) - 그런데, 조수아 벤틀리가 제시한 저 수정안도 low 와 high 의 값의 합이 unsigned int 의 범위를 넘게 된다면 여전히 Overflow 문제가 생길 수 있다... -_-; 결국 ASSERT 등을 사용해서 인덱스의 범위 내에서만 사용이 가능하도록 제약을 걸거나, Overflow 를 피하려면 여유있게 long long 과 같은 64 비트 변수를 쓰는 것이 보다 안전할 것 같다. 
'Contest > Algorithm' 카테고리의 다른 글
|
위 내용하고는 다른 내용인데..
최근에 발견한 win32 api 버그는 머냐면... 소켓통신 관련된 모듈인데..
xp 에서는 잘되는 놈인데... vista 랑 windows7 에서는 버그가 있더라고..왜그러나 하고 디버깅을 해보니까...
ip 를 처리하는 모듈이 vista 이상의 os 에서 default 로 활성화 되어 있는 ipv6 땜에 ipv6 로 ip 를 받았다가
내부적인 코드에서 문제가 발생하고 있더라고...
또 하나 위하고는 다른 내용인데...
아폴로 XX 호 던가... 그 40초만에 로켓트가 터져버린 사건...
그사건의 원이이 바로.. 저런거 때문이었었다지.... 하드웨어적인 결함이 아닌 숫자형 type 하나를 잘못쓰는것으로 인하여
로켓트가 폭발해버리는..
오호... 그런 일이 있었군...
근데 그 공중폭팔한 아폴로 호는 내가 듣기로는 연료 계통에서 문제가 있어서 폭팔했다고 하던데.. 소프트웨어 문제도 있었낭..??
포스팅이 프로그래밍 관련 일색이구나....
일상에서는 포스팅 할 것이 없어진 것이냐...
있긴한데 요새 자꾸 게을러져서...
그리고 그냥 공부하는 거 가끔 블로깅 하는게 나한테 맞는 거 같아서...
개인적인 이야기 블로그에 올리는 건 별로 안좋아해서..
비밀댓글입니다
반갑습니다... 저 님 블로그 애독자예요 ^^