BigInteger를 구현해보자 - 3. 음수의 표현, 뺄셈

Posted by 적분 ∫2tdt=t²+c
2009.03.29 01:13 프로그래밍/Multi precision
bigint에서 음수는 2의 보수 표기법을 사용하도록 한다. 그것이 덧셈 뺄셈에 간편하기 때문.
다음 함수는 2의 보수를 취해주는 함수이다. 즉 부호를 바꿔주는 함수.

bigint_neg함수는 bigint의 부호를 바꿔주는 놈이고, createnegcopy는 부호가 반대인 놈을 복사해서 만들어주는 놈이다.
뺄셈은 2의보수를 취하고 더해주면 되지만, 그렇게 한다면 뺄셈을 할 때마다 2의보수를 취해야 하기 때문에 따로 구현하도록 한다.
자 다음 함수들을 먼저 만든다.

두 u4배열을 빼는 함수(받아내림 계산하고, 최상위자리에서 받아내림했을 경우 1을 리턴)

u4배열의 특정자리를 src만큼 빼주는 함수 (받아내림 계산하고, 최상위자리에서 받아내림했을 경우 1리턴)


자 이를 토대로 두 bigint를 빼는 함수를 만든다. 더하는 함수와 매우 유사하다.

dest와 src의 길이를 비교해서 빼준다. dest와 src의 길이가 n이라면, 받아내림이 하나도 없을 경우 n회의 뺄셈을 하게되고, 최악의 경우 모든 자리에서 받아내림이 발생하면 2n회의 뺄셈을 하게되므로, 이 뺄셈 함수의 시간 복잡도는 덧셈과 마찬가지로 O(n)이 된다.
Tags
이 댓글을 비밀 댓글로
    • 초보
    • 2016.12.15 07:26
    u4 배열의 마지막은 부호비트인가요?
    그러면 마지막 부호비트 전체가 1인경우( 0xFFFFFFFF) 라면
    음수라 이말씀이신가요?
    • 2의 보수 표현법에서는 최상위비트가 1일 경우 음수로 처리합니다. u4 배열 뒤로 갈수록 더 상위 자리수를 표현하도록 규칙을 세웠으니, 가장 마지막 요소의 최상위비트가 1일 경우 음수가 됩니다.