Silicon to Scripting 7

Representing numbers in binary and being able to add them is a large step in building a computer. The specific encoding we chose helped us in constructing the physical logic gate by making it simple.

So when it comes to negative numbers and subtracting, we could try to pick an encoding that helps us keep it simple.

Instead of figuring out how to do both addition and subtraction, when we want to subtract y from x: x−yx - y, we could make yy negative and then add it to xx: x+(−y)x + (-y). But right now, we only can represent positive numbers with our encoding.

Again, try to come up with an encoding for negative numbers, it’s a good exercise.

Two’s Complement

Two’s complement is an example of a radix complement.

— Wikipedia

[A radix complement] is a technique to encode a symmetric range of positive and negative integers in a way that they can use the same algorithm for addition throughout the whole range.

— Wikipedia

This is the encoding that allows us to use x+(−y)x + (-y) instead of x−yx - y.

There are a few parts to this, so lets go through them one by one.

We need to “sacrifice” one bit of numerical storage for the “sign storage”. Modern computers use the highest (leftmost) bit.

1 001 => negative
0 011 => positive

Lets firgure out the actual encoding now.

1+(−4)=−31 + (-4) = -3

0001 + ... = ...

If we try and use the same encoding, it doesn’t work

0001 + 1100 = 1101 # wrong

What can we do to make that work? If we use Two’s Complement, it does work.

0001 + 1100 = 1101

But how did we get there?

A more theoretical answer can be found on wikipedia. As for the algorithm, it is

  1. Start with the absolute value of the number
  2. Compute the bitwise inversion (invert all bits)
  3. Add 1 to the number, ignoring overflows

Lets take −4-4 as an example:

  1. 0100
  2. 1011
  3. 1100

The “add 1” can be hard to reason why it’s there, but lets look at the range of number for a “signed 4 bit integer”: [−4,3][-4, 3]. The negative range always includes one more number because the original negative range of [−3,−0][-3, -0] was shifted because 00 and −0-0 are the same.

references

part 8