9A. Appendix Two complement system

This chapter requires some level of mathematical knowledge to understand.

The two-complement system is a simple and elegant way to represent negative numbers inside a computer. To understand the two-complement system you need to understand the basics of modular arithmetics and congruence.

a ≡ b (mod c) means that a and b have the same remainder divided by c. For example, since 7 % 5 = 2 and 2 % 5 = 2, so 7 ≡ 2 (mod 5). When a ≡ b (mod c), we say that a and b are congruent modulo c.

The most basic property of congruence is, that is two numbers are congruent by some modulus, then the difference between two numbers is divisible by the modulus. For example, since 7 ≡ 2 (mod 5), 7 - 2 = 5 is divisible by 5. Here divisible means that the division leaves no remainder. Mathematical notation for divisibility is a <vertical bar> b. We'll use | as a symbol for a vertical bar in this section.

Normally | means bitwise OR, or logical OR (||).

The basic property of congruence is that multiplication and addition preserve congruence. For every a ≡ b (mod c) and x ≡ y (mod c), a + x ≡ b + y (mod c) and a * x ≡ b * y (mod c).

Proof) If two number is divisible by c, then their sum is also divisible by c. Also, if a number is divisible by c, it`s multiple by integer is also divisible by c. Considering this, c | b-a, c | y-x. So c | (b-a) + (y-x) = (b+y) - (a+x), and c | b(y-x) + x(b-a) = by-bx+bx-ax = by-ax.

The computer represents an integer by its remainder divided by 2^32. Remainder always stays in a range between 0 and (2^32 - 1). Hence, -1 is represented as 4294967295 (= 2^32 - 1) inside computer. For convenience, let's define c = 2^32. Here -1 ≡ c-1 (mod c) and 3 ≡ 3 (mod c), -1 * 3 ≡ (c-1) * 3 (mod c). This means that -3 ≡ (whatever -1 is internally represented inside computer) * 3 (mod c)

So in euddraft, if we say -1 * 3, internally computer is computing 4294967295 * 3, but we don't need to care about that since we know that its value will be congruent to -3 modulo 2^32. Since multiplication and addition are preserved in modular arithmetics, we can just think that some value congruent to -3 modulo 2^32 as -3 during addition, subtraction, and multiplications. This won't hold in division and comparison since those aren't preserved in a congruence world.

See wiki page on two-complement system for more info.