magic of big_int, from uint to int

Coordinator
Mar 17, 2014 at 1:41 PM
Edited Mar 17, 2014 at 1:43 PM
as most of developers know, when negating a number, the operation is bit-wise NOT then add one. since we are using complement in computer system. so let me explain first, why we need complement.
the processor knows nothing about the 'signed' integer, i.e. no matter signed or unsigned int, the basic add / sub / multiply / divide operations are the same to the processor.
there are two flags to shows the 'overflow' status of an integer operator. CF, known as Carry Flag, will be 1 when the operation results to be incorrect because we need to carry the result to higher bit, or borrow 1 from the higher bit. SF, known as Sign Flag, will be 1 when the operation results to change the most significant bit, i.e. 'sign bit'.
let's simulate an 8-bit processor with signed integer operations,
scenario 1)
00000000 +
11111111
11111111 =
the CF = 0, SF = 1, the 'correct' result should be -1 [0 + -1 = -1]
11111111 +
11111111
11111110 =
the CF = 1, SF = 0, the 'correct' result should be -2 [-1 + -1 = -2]
01111111 +
10000001
00000000 =
the CF = 1, SF = 1, the 'correct' result should be 0 [127 + -127 = 0]
01111111 +
11111111
01111110 =
the CF = 1, SF = 0, the 'correct' result should be 126 [127 + -1 = 126]
01111111 +
00000001
10000000 =
the CF = 0, SF = 1, the 'correct' result should be 128 [127 + 1 = 128], but the actual result is -128, since we cannot express 128 in 8 bit signed integer.
but anyway, the expressions above shows, when we are using complement, the operations of signed and unsigned integer will be the same.

this works well in the processor word-width integer operations, since the processor can bit-wise NOT and add one in not more than two instructions. but to the big_int, it will become a disaster. we may have 10K integers to present one big_int, use O(n) to negate it is not acceptable. so from big_uint to big_int, the very traditional way is used, one bit / bool value in big_int to show it's negative or positive. while we need to take care of sign when performing operations, every operations.

so following threads will be 'magic of big_uint' instead of 'magic of big_int'.