Contents

1 About this module

• Prerequisites: 0282, 0283, 0284
• Objectives: This module explores how negative values are represented in binary.

2 Value vs. Number (Representation)

The value represented by the base 10 number -45 is a quantity. “-45” is a way to represent this quantity in a way that most people understand. In other words, the representation “-45” is a means for communicating a quantity.

Inside a solid state binary digital computer, all processing hardware is made from transistors. We assign a meaning of 1 or true to a high voltage, and a meaning of 0 or false to a low voltage. Everything has to be represented using these two states.

In module 0282, we discussed how values can be represented by binary numbers. That handled non-negative values well. However, since we are used to the concept using the negative sign “-” to indicate a value is negative, we may feel stumped when we need to represent negative values using just 0s and 1s.

3 Arithmetic Negation

In arithmetic, negation is used to turn a non-negative value into a negative value. In other words, $-\left(45\right)=-45$ (the left hand side uses “-” as an operator, where the right hand side uses “-” to indicate a number is negative).

Arithmetic negation is also its own inverse. This means $-\left(-\left(x\right)\right)=x$.

We also know that the sum of a number and its arithmetic negation is 0. In other words, $x+\left(-\left(x\right)\right)=0$.

It follows that adding the negated value is the same as subtracting the original value, that is $x-y=x+\left(-\left(y\right)\right)$.

What if we are to find a bit-wise operation that has all the same property as arithmetic negation? Would that be our way to represent negative values?

4 The Number Circle

Before we answer the question about the bitwise operator that has the same properties as arithmetic negation, let us first explore the concept of a number circle.

Given that we are limited to 4 binary digits (4 bits), we know the values that can be represented range from 0 (represented by $0000_2$) to 15 (represented by $1111_2$). However, instead of looking at this as a number line segment, let’s tie the two ends and make a circle out of it.

Now imagine that we pin this wheel to a board with a marker, much like the wheel used in Wheel of Fortune (the game show). The marker points to the value currently represented by the wheel.

For discussion purposes, let us arrange the numbers so that the values increase in clockwise direction (consistent with analog clocks). Of course, there is a slight problem because 0 and 15 are right next to each other, breaking the increasing order rule. We’ll deal with this later.

Given this set up, adding a value $x$ is to rotate the wheel counter-clockwise $x$ steps because the wheel is what is rotating, the marker does not move. Likewise, subtracting a value $x$ is to rotate the wheel clockwise.

For example, when the marker is on 5, adding 2 is to rotate the wheel counterclockwise by two positions, the marker ends up point to 7.

This analogy works for the most part. However, what happens when the marker is on 0, but we rotate the wheel clockwise by 1? The marker is then on 15, which does not seem to make sense because $0-1$ should not be 15.

Now is a good time to label the wheel with binary numbers. When the marker is on $0000_2$, and we rotate the wheel clockwise by one slot, the marker ends up on $1111_2$. One value that can be represented by $1111_2$ is 15, but this is an interpretation!

But if we assign the value of -1 to the slot labeled $1111_2$? Why not? We can continue with $1110_2$ representing -2 and so on. We keep doing this until half the slots are representing negative values, while the other half are non-negative values. 0 is represented by $0000_2$ because it is a non-negative value.

The largest non-negative value left on the wheel should be 7, represented by $0111_2$.

The new values labeled on this wheel continues to work with rotation of the wheel. For example, if the marker is on -3 ($1101_2$), and we rotate the wheel counterclockwise by two slots, the marker will be on -1 ($1111_2$).

Hmmm, we may have found a way to represent negative values!

4.1 But which value is 1111(2) representing?

Is it 15? Or is it -1?

The question is what do we care? If the adder and subtractor mechanisms introduced in modules 0283 and 0284 work so that $-3+2=-1$ and $13+2=15$ because $1101_2+0010_2=1111_2$, there is no need to know whether $1111_2$ represents -1 or 15!

The only time when this matters is when we need to compare. In other words, if we need to decide whether $0000_2<1111_2$, then the values represented by the bit patterns matter. If $1111_2$ represents -1, then $0000_2<1111_2$ is false. On the other hand, if $1111_2$ represents 15, then $0000_2<1111_2$ is true!

We’ll deal with comparison in another module.

5 Back to Arithmetic Negation

Given that we accept that $1111_2$ as a 4-bit number can represent the value of -1, which bitwise operator can turn the bit pattern representing 1, $0001_2$, into the bit pattern representing -1?

First of all, let us observe that $10000_2-00001_2=01111_2$. In other words, by adding one more bit and make the most significant bit a 1, we can convert the representation of 1 into the representation of -1 by a simple binary subtraction. You can try to convert the representation of -1 into the representation of 1.

But this approach is not very helpful if the width of numbers is fixed. We cannot just arbitrarily make some numbers one bit wider in the processor. However, there is a trick to get this done. Let us assume $x$ represents a 4-bit bit pattern.

In other words, we “cheated” by expressing $10000_2$ as $1111_2+0001_2$, then we use the commutative property of addition to move the terms around.

Let us now focus on the expression $1111_2-x$ knowing that $x$ is a four-bit pattern. Let $x_i$ denote the $i$th bit of $x$. This subtraction is special because there is no chance of borrowing. For each column of the subtraction, the minuend is 1, which means the difference is $1-x_i$, but that is the same as $!x_i$.

First of all there is no borrow in any of the digits because for each bit, the minuend is 1, and $b\left(1,x_i\right)$ is guaranteed to be 0. Furthermore, $r\left(1,1\right)=0$ and $r\left(1,0\right)=1$. This is why $r\left(1,x_i\right)=!x_i$.

Looking at $x$ as a four-bit pattern, this means $1111_2-x$ is the same as a bitwise-not. Bitwise-not (flipping each individual bit) is also known as one’s complement. Let us use $c_1\left(x\right)$ to represent the one’s complement of $x$. Then we can conclude that:

$10000_2-x=c_1\left(x\right)+0001_2$

We define two’s complement as $c_2\left(x\right)=c_1\left(x\right)+1$. In other words, two’s complement is one’s complement plus one.

Two’s complement is our bitwise operator to perform the equivalence of arithmetic negation. In other words, given that $v$ is represented by a bit pattern $x$, then the value $-v$ is represented by the bit pattern $c_2\left(x\right)$.

It is a good exercise to check whether $c_2\left(x\right)$ meets the requirements of $c_2\left(c_2\left(x\right)\right)=x$, $x+c_2\left(x\right)=0$ and given another bit pattern $y$, $y-x=y+c_2\left(x\right)$.