Module 0260: Signed integer representation

Tak Auyeung, Ph.D.

January 30, 2017

1 About this module

Prerequisites: 0255
Objectives: This module explores how signed integers are represented as binary numbers.

2 Signed integers

Signed integers represent values that are non-negative (including zero) and those that are negative, such as $- 1$ . In our normal notation, the unary minus operator ( $-$ ) is used to denote negative. In a system where everything is 0 or 1, however, there is no sign to indicate whether a numbe is negative or not.

There are alternatives to use 0 and 1 to represent the sign of a value. For example, we can allocate a single bit so that if this bit is 1, the number is negative, if this bit is 0, the number is non-negative. However, such a method renders the adder and subtractor logic useless.

In order to be able to better utilize transistors in a processor, we need a representation of negative integer values so that the logic gate implementation of the adder and subtractor can be used regardless of whether a value of a representation is signed or not.

3 Back to subtractors

Let us consider combinations of four bits. There are only $2^{4} = 16$ of them. If we only need to represent non-negative values, we can use all 16 combinations, from $000 0_{2}$ to $111 1_{2}$ to represent the integers from 0 to 15.

If we need to represent integer values that are both negative and non-negative, however, we will need to assign negative values to some of the these bit patterns. The only question is how to do this assignment. The objective to reuse the adder and subtractor logic helps us choose the assignment.

What we need to do is to consider the bit pattern of $000 0_{2} - 000 1_{2}$ . Because $000 0_{2}$ represents zero (this one is obvious!), and $000 1_{2}$ represents 1, it makes sense that we can choose the result of $000 0_{2} - 000 1_{2} = 111 1_{2}$ to represent the value of $- 1$ . The same applies to $000 0_{2} - 001 0_{2} = 111 0_{2}$ to represent $- 2$ and so on.

In fact, it makes sense to use $000 0_{2} - w x y z_{2}$ to represent the arithmetic negation of the value represented by $w x y z_{2}$ (where each letter represents a bit). For notation purposes, we use $v$ to denote the value represented by the bit pattern $w x y z_{2}$ .

4 Twos’ complement

How do we perform $000 0_{2} - w x y z_{2}$ ? Well, the same way as do we any binary subtraction! Due to the ﬁrst number being zero ( $000 0_{2}$ ), however, we have some quick tricks to get this done.

Because we are only interested in the least signiﬁcant four bits of the subtraction, $000 0_{2} - w x y z_{2}$ and $1000 0_{2} - w x y z_{2}$ would yield exactly the same result as far as the least signiﬁcant four bits are concerned. The only diﬀerence is whether there is a leftover borrow from bit 4.

$1000 0_{2}$ is $111 1_{2} + 000 1_{2}$ . So now we have the following:

\begin{array}{l} 0 - v & = 000 0_{2} - w x y z_{2} & (in binary) \\ = 1000 0_{2} - w x y z_{2} & (becausewe only need four bits) \\ = (111 1_{2} + 000 1_{2}) - w x y z_{2} & (expand) \\ = 111 1_{2} - w x y z_{2} + 000 1_{2} & (associative law applied) \\ = (111 1_{2} - w x y z_{2}) + 000 1_{2} \end{array}

As it turns out, $111 1_{2} - w x y z_{2}$ is a special subtraction, as well. Because we are always subtracting a zero or a one (represented by $w$ to $z$ ) from a constant of $1$ , this is the same as boolean negation. In short, $1 - w = \bar{w}$ , $1 - x = \bar{x}$ and so on. The boolean negation is applied to each bit of $w x y z_{2}$ . In C/C++, this is represented by the bit-wise not operator (~).

Now we can ﬁnish our equation:

\begin{array}{l} 0 - v & = (111 1_{2} - w x y z_{2}) + 000 1_{2} & (from the previous derivation) \\ = \sim v + 000 1_{2} & (bitwise not in place of binary subtraction) \\ = \sim v + 1 & (one is the same regardless of base) \end{array}

Of course, this rather weird way of looking at arithmetic negation is only applicable when we limit our view to a ﬁxed number of bits. In our examples, the width of operations is 4-bit. The principle, on the other hand, applies to integers represented by any number of bits.

$C2 (w) = \sim w + 1$ is called two’s complement because bitwise negation is called one’s complement.

5 Range of signed values

Two’s complement does not automatically suggest the range of signed values to be represented by $n$ bits. All it says is the bitwise operation $C2$ is equivalent to arithmatic negation.

However, $C2$ can be used to help us here. Unless $x = 0$ , $- x \neq x$ . Because $C2$ is equivalent to arithmatic negation, we can also say that unless $x = 0$ , $C2 (x) \neq x$ .

We can plug in individual 4-bit numbers to test this requirement. $C2 (000 0_{2}) = 000 0_{2}$ , but that’s okay because it is zero. $C2 (000 1_{2}) = 111 1_{2} \neq 000 1_{2}$ , the requirement is met. This works all way until we get $C2 (100 0_{2}) = 100 0_{2}$ ! This means we have hit a limit due to the limited number of bits (4 in this case).

Then the question is what should the bit pattern $100 0_{2}$ represent? We have to choices, it can be $8$ or $- 8$ . The correct choice is $100 0_{2} = - 8$ as a signed number.

The superﬁcial reason is that we already have 0 as a non-negative number, so the range of non-negative values only go from 0 to 7 for 8 of them. As a result, the negative values go from -1 to -8 also to have 8 of them.

The more rigorous reason is that we treat the most signiﬁcant bit as the “sign” bit. All the negative values are represented by bit patterns with the most signiﬁcant bit being a one. Given numbers are represented in $n$ -bit patterns, bit $n - 1$ is the sign bit.

In general, given $n$ bits, the range of integer values is from $- 2^{n - 1}$ to $2^{n - 1} - 1$ .

6 Comparing unsigned values

A comparison is, essentially, a subtraction where the diﬀerence is not important. Assuming bit patterns represent unsigned values, the borrow ﬂag can be used to indicate ordering of values.

Assume that a binary subtractor performs the n-bit subtration $x - y$ . The borrow of bit $n$ is 1 iﬀ $x < y$ . This makes sense because a borrow of one is triggered only if a subtraction tries to subtract more than there is available.

Can we actually prove that “a subtraction borrows from bit $n$ only if the bit 0 to bit $n - 1$ of the minuend is less than bit 0 to bit $n - 1$ of the subtrahend?”

As a matter of fact, we can! Again, the proof itself is CISP440 material, but included here for the curious and those desire rigorous mathematical proofs!

This is done by proof-by-induction. Let us use $x$ to denote the minuend, $y$ to denote the subtrahend. $x_{i}$ is bit $i$ of $x$ , and $y_{i}$ is bit $i$ of $y$ . We also we the notation $x [i : 0]$ to specify the bit pattern from bit 0 to bit $i$ of $x$ .

The base case is when we subtract a 1-bit number from a 1-bit number. According to the $B (x, y)$ function, we only borrow from bit 1 iﬀ we have $0 - 1$ for bit 0, and $0 < 1$ .

For the induction step, we assume the theorem is true up to an n-bit subtraction. In other words, we assume that we borrow one from bit $n$ only if $x [n - 1 : 0] < y [n - 1 : 0]$ . Furthermore, let $b$ be the borrow bits where $b_{i}$ is the borrow from bit $i$ .

Now we are ready to perform the last step. From the structure of a subtraction, the borrow from bit $n + 1$ is as follows:

\begin{array}{l} b_{n + 1} & = B (x_{n}, y_{n}) + B (R (x_{n}, y_{n}), b_{n}) & (by structure of subtractor) \\ = (\bar{x_{n}} y_{n}) + B ((\bar{x_{n}} y_{n}) + (x_{n} \bar{y_{n}}), b_{n}) \\ = (\bar{x_{n}} y_{n}) + \bar{((\bar{x_{n}} y_{n}) + (x_{n} \bar{y_{n}}))} b_{n} \\ = (\bar{x_{n}} y_{n}) + (\bar{(\bar{x_{n}} y_{n})} \cdot \bar{(x_{n} \bar{y_{n}})}) b_{n} \\ = (\bar{x_{n}} y_{n}) + ((x_{n} + \bar{y_{n}}) \cdot (\bar{x_{n}} + y_{n})) b_{n} \\ = (\bar{x_{n}} y_{n}) + ((x_{n} \bar{x_{n}} + x_{n} y_{n} + \bar{y_{n}} \bar{x_{n}} + \bar{y_{n}} y_{n})) b_{n} \\ = (\bar{x_{n}} y_{n}) + ((x_{n} y_{n} + \bar{x_{n}} \bar{y_{n}})) b_{n} \\ = (\bar{x_{n}} y_{n}) + ((x_{n} y_{n} + \bar{x_{n}} \bar{y_{n}})) b_{n} \\ = \bar{x_{n}} y_{n} + (\bar{x_{n}} + y_{n}) b_{n} \end{array}

We have seen this derivation from a previous module, but the signiﬁcance is diﬀerent here.

In order for $b_{n + 1}$ to be a one, $\bar{x_{n}} y_{n}$ can be true. But this means $x_{n} = 0 \land y_{n} = 1$ , which also means $x [n : 0] < y [n : 0]$ .

If $\bar{x_{n}} y_{n}$ is not true, then $(\bar{x_{n}} + y_{n}) b_{n}$ has to be true if $b_{n + 1}$ is true. Let’s see what this means.

$(\bar{x_{n}} + y_{n})$ is true iﬀ $x_{n} = y_{n}$ because we already know at this point $\bar{x_{n}} y_{n}$ is false. A true table can be used to illustrate this. We will also need $b_{n}$ to be true. Our induction assumption says that $b_{n} = 1$ iﬀ $x [n - 1 : 0] < y [n - 1 : 0]$ .

Because we also know that $x_{n} = y_{n}$ , we can now conclude that $x [n : 0] < y [n : 0]$ . This concludes the proof by induction.

The bottom line is that $b_{i} = 1$ iﬀ $x [i - 1 : 0] < y [i - 1 : 0]$ .

7 Comparing signed values

It is a little more diﬃcult to ﬁgure out the ordering of signed values represented in binary. Intuitively, if $x < y$ , then $x - y < 0$ , and so the sign bit of the result (diﬀerence) should be set.

This is true in some cases. For example, $- 1 < 1$ . In four-bit signed representations, $111 1_{2} = - 1$ and $000 1_{2} = 1$ . The subtraction yields, $111 1_{2} - 000 1_{2} = 111 0_{2}$ , and the sign bit is set.

However, in some other cases, the sign ﬂag is not set when “it is supposed to.” Let us take a look at this comparison: $- 4 < 5$ . In four-bit signed representations, $110 0_{2} = - 4$ , $010 1_{2} = 5$ . $110 0_{2} - 010 1_{2} = 011 1_{2}$ , the sign bit of the result is not a one!

This can be explained by $- 4 - 5 = - 9$ , and that is less than the most negative value that can be represented in four bits. In other words, we have an “overﬂow” situation. Because $- 9$ cannot be represented by four bits, it “wraps” around to the representation of $7$ .

Let us use the notation that $x$ is the minuend, $y$ is the subtrahend, $d$ is the diﬀerence, and subscripts indicate bit position. Assume all values are in $n$ bit representation. Then the overﬂow ﬂag (it is a one iﬀ a the result of a subtraction exceeds the limits of representations of signed integers) is deﬁned as $O = x_{n - 1} \bar{y_{n - 1}} \bar{d_{n - 1}} + \bar{x_{n - 1}} y_{n - 1} d_{n - 1}$ .

This means we have an overﬂow condition whenever the sign of subtrahend and diﬀerence are the same, and it is opposite to the sign of the minuend. This makes sense because it means $(- ve) - (+ ve) = (+ ve)$ or $(+ ve) - (- ve) = (- ve)$

Although the sign ﬂag of the diﬀerence $S = d_{n - 1}$ alone is not suﬃcient to indicate ordering of signed values represented in binary, together the ﬂags $S$ $O$ can. We can deﬁne a new ﬂag $L = \bar{S} O + S \bar{O}$ to indicate the minuend is less than the subtrahend.

One way to interpret the deﬁnition of $L$ is that when $O = 1$ , it means “the proper $S$ ﬂag should be the opposite”. After a subtraction of signed values represented in binary, we want either “the $S$ ﬂag is set and it is proper” or “the $S$ ﬂag is cleared, but should have been the opposite!”