W1032 Negative Integers

Within these castle walls be forged Mavens of Computer Science ...

— Merlin, The Coder

Prerequisites

• W1031 Positive Integers

Encoding Options

Reserved Bit

What methods might we use to encode negative integers? As a first approach, perhaps we can use one of the bits of our word to represent the sign. Let's consider a single-byte word and the number $5_{10}$. This may be encoded as:

Positive 5

If we were to reserve the most-significant bit, bit seven, to indicate whether our number was positive or negative, we can use the remaining seven bits to store the absolute value of the number. In such a case, the number $-5_{10}$ would be encoded as:

Negative 5, Reserved Bit

Initially this may appear to be a good solution, but let's explore further.

Observe

Observe, Ponder, and Journal: : Section 1

Reserved Bit Encoding

1. How would $+11_{10}$ be encoded?
2. How would $-11_{10}$ be encoded?
3. How would you add these two numbers ($+11_{10}+-11_{10}$) in binary?
4. How many alternative representations are there for the number 0?
5. Given the above, do you think that this method of encoding is ideal? Why or why not?

Let's consider what our goals should be for an ideal encoding scheme.

• We shouldn't waste bit patterns (in other words, each bit pattern should identify a unique number)
• We should easily be able to add positive numbers to one another
• We should easily be able to add negative numbers to one another
• We should easily be able to add numbers of opposite sign

Complements

Yinyang

A complement is something that is required to complete a whole. Colors have complements, shapes have complements, and numbers have complements. In the following sections we'll investigate some common numerical complements.

Nines' Complement

Consider the aforementioned goals; are we able to meet them? Consider the decimal number system and a need to subtract two numbers. (Remember that when subtracting M - S we refer to M as the minuend and S as the subtrahend.) Let's subtract 7 - 3 to obtain 4. Is there another method that we can use to obtain the same result? We can use nine's complement by subtracting each digit of the subtrahend from 9. In this case, we'll have 9 - 3, or 6. If we then add this to our original minuend, 7, we'll have 7 + 6 = 13. But wait! That's not four. However, if we drop the carry and add one we'll have 4.

Let's try this with some larger numbers, 742 - 359. The result is 383. The nine's complement of the subtrahend is 9-3=6, 9-5=4, and 9-9=0, yielding 640.

Helpful Hint

A shortcut to obtaining nine's complement is simply to use the same number of 9's as are present in the subtrahend to form a minuend and then perform the subtraction. In the above example, this would simply be 999 - 359 = 640.

Continuing, we'll add this number to our original minuend, 742, and obtain 742 + 640 = 1,382. Dropping the carry and adding one we'll have 383, the desired result. For decimal numbers, the algorithm is therefore:

1. Take the nine's complement of the subtrahend
2. Add this number to the original minuend
3. Drop the carry
4. Add one

Tens' Complement

We can simplify this a bit by adding the one when calculating the complement of the subtrahend. For the decimal number system, this would be called the ten's complement. Our improved algorithm is therefore:

1. Take the ten's complement of the subtrahend
2. Add this number to the original minuend
3. Drop the carry

Let's try it. Given 9,228 - 6,125 = 3,103. Using our algorithm:

1. Take the ten's complement of the subtrahend -> 9,999 - 6,125 = 3,874 -> 3,874 + 1 = 3,875
2. Add this number to the original minuend -> 9,228 + 3,875 = 13,103
3. Drop the carry -> 13,103 without carry = 3,103 ✓

Ones' Complement

This same method can be used for binary numbers, but in the case of binary numbers, it's even easier! The complement of 0 is 1 while the complement of 1 is 0.

Twos' Complement

As in the case of tens' complement, twos' complement can be obtained by adding one to one's complement.

	Coming Soon
	Add section on internals including CPU status flags

References

• Complements (Wikipedia)