**SIMPLISTIC EXPLANATION OF BINARY
NOTATION**

In the summer of 1962, I was privileged to be among the top 20 (out of 800 applicants) winners of a National Science Foundation grant to learn computer programming (and selected number theory topics from Peano’s Postulates to elementary calculus) at St. Louis University. But even more notably, we got to meet the head of the mathematics department, who organized and taught the lecture series. This was our introduction to computers.

Most
everyone recognizes that for any given string of “n” decimal digits d_{i}
such as

D_{n}
= { d_{n-1}, d_{n-2}, …, d_{2}, d_{1}, d_{0 }},
where d_{i} e { 0,1,2, …, 8, 9 }

then
those digits to the left correspond to ever increasing powers of ten. The value
of the string can be represented by the “V_{b}()” function where “b” is
the base; and for b = 10, we have

V_{10}(D_{n})
= d_{n-1} * 10^{n-1} + d_{n-2} * 10^{n-2 }+ … +
d_{1} * 10^{1 }+ d_{0} * 10^{0}

or more compactly

V_{10}
(D_{n}) = _{}

Since computers make use of electronic elements having only two possible states, these are best described using the binary number system. For a string of “n” binary bits such as

B_{n}
= { b_{n-1}, b_{n-2}, …, b_{2}, b_{1}, b_{0 }},
where b_{i} e
{ 0,1 }

and
as before the value “V_{2}()” function is

V_{2}
(B_{n}) = b_{n-1} * 2^{n-1} + b_{n-2} * 2^{n-2
}+ … + b_{1} * 2^{1 }+ b_{0} * 2^{0}

or

V_{2}
(B_{n}) = _{}

Another way of representing a string of binary digits is

B_{n} = { b_{n-1}, b_{n-2}, …, b_{2}, b_{1,}
b_{0 }} = B[n-1:0]

where
the double subscript represents a range of “n” bits and so for a single
subscript B[k] = b_{k }for (n-1) <= k <= 0. Note that B[n-1] is
called the most significant bit (msb) and B[0] = b_{0 }and is called
the least significant bit (lsb).

Yet another notation is to simply append the base as a trailing subscript. For example, the following values are equivalent

11_{2} = (1)*2 + (1)*1 = 3_{10}

110_{2} = (1)*4 + (1)*2 = 6_{10}

1111_{2 }= 8 + 4 + 2 + 1 = 15_{10}

10
0001_{2} = 32 + 1 = 33_{10}

and so forth. Alternatively, we could easily expand to any arbitrary base. For an arbitrary vector

W_{n}
= { w_{n-1}, w_{n-2}, …, w_{2}, w_{1}, w_{0 }},
where each 0 <= w_{i} _{ }<= (b – 1), then the value
function becomes

**V _{b}(W_{n})
= w_{n-1} * b^{n-1} + w_{n-2} * b^{n-2 }+ … + w_{1}
* b^{ }+ w_{0} = _{}**

**INVERTING A BINARY STRING**

The
inverse of a single binary bit “a_{i}”, is simply defined as

ā_{i} =1 if a_{i}=0

and

ā_{i} =0 if a_{i}=1

Another way of writing this is

**
ā**_{i}** = 1 - a _{i}**

For a string of “n” bits starting from

A_{n} = A[n-1:0] = { a_{n-1}, a_{n-2}, …, a_{2},
a_{1}, a_{0 }},

then the notation for the inverse is simply

Ā_{n} = Ā[n-1:0] = { ā_{n-1}, ā_{n-2}, …, ā_{2},
ā_{1}, ā_{0 }}.

And
the value, V_{2}(Ā), of a string of “n” inverted bits is

V_{2}
(Ā_{n}) = _{}= _{}= _{}

Also note that the magnitude of a binary string of all ones

_{}

and

_{}

**V _{2}
(**

or

** **

**V _{2}(**

What
this means is that inverting a binary string, A_{n}, is exactly
the same operation as subtracting the string from a series of “n” continuous
ones, i.e. 2^{n} – 1. In this sense A_{n}, and its
inverse Ā_{n, }are the **one’s compliment** of each other. For
example, if n = 3 we can construct the following table

where the last column on the right duplicates the previous binary operation but in decimal notation for clarity.

**ONE’S COMPLIMENT**

In
“one’s compliment” notation binary bit strings are used to represent both
positive and negative numbers. This is accomplished by arbitrarily assigning
exactly half of all the possible patterns to each range. For increasingly
positive numbers, the straightforward values of V_{2}(A_{n})
increase starting from zero whereas for increasingly negative numbers, the V_{2}(A_{n})
decrease in value. Consider for example,
the table of all possible 3 bit strings, A_{3}, where we have also
introduced a one’s compliment function, Ones(A_{3}), which returns the
one’s compliment decimal value.

This table can be formally expressed in simple equations as shown below:

a) Zero is represented by two separate strings {0,0,0} and {1,1,1} corresponding to something like +0 and -0. This is inefficient.

b) All 1’s compliment strings with positive decimal values start with a zero,

**Ones(A _{n}) = V(A_{n})**

** ** or

**Ones(A _{n}) = **

when the msb
a_{n-1 }=_{ }A[n-1] = 0.

** **

c) All 1’s compliment strings with negative decimal values start with one,

**Ones(A _{n}) = V(A_{n}) - **

**
**or

**Ones(A _{n}) **

** **

when the msb
a_{n-1}= A[n-1] = 1.

The
negative values run backwards in that the largest V_{2}(A_{n})
gives the smallest decimal value in Ones(A_{n}).

d)
The full range of values is **(1- ****2 ^{n-1}**

In
support of the above equations for the inverted bit string Ā_{3}, the following table lists the operations for all
3-bit strings as shown below:

An
interesting features of one’s compliment from the above table is that if a
given binary string, A_{n}, has a positive value, then the inverted binary string, Ā_{n} seems to represent the corresponding negative value. But more formally,

When
ā_{n-1 }= 0, Ones(Ā_{n}) = V(Ā_{n}). And since a_{n-1 }= 1, Ones(A_{n}) = - V(Ā_{n}). Then

**Ones(****Ā**_{n}**)
= -Ones(****A**_{n}**).**

Likewise,
if ā_{n-1 }= 1, Ones(Ā_{n}) = -V(A_{n}). And since a_{n-1 }= 0, Ones(A_{n}) = V(A_{n}). And
so again, and for all values,

**Ones(****Ā**_{n}**)
= -Ones(****A**_{n}**).**

Basically, inverting the bit string always multiplies the 1’s compliment value by minus one.

EXAMPLE

To
summarize, to get the 1’s compliment value of the 6-bit string A_{6 }=
110101_{2} , we calculate

Ones(110101_{2})
= V_{10}(110101_{2}) – (2^{6}-1) = (32+16+4+1) – (64-1)
= 53 – 63 = -10_{10}

To
convert from a negative number to a positive number, we simply invert the bit string
so that Ā_{6 }= 001010_{2}
and

Ones(īī ōī ōī_{2}) = Ones(001010_{2}) = (1)*8 + (1)*2 = +10_{10}

**TWO’S COMPLIMENT**

The purpose of two’s complement notation is also to reassign bit patterns to represent negative numbers but in a slightly more efficient manner than for one’s compliment. In particular, the double assignment of zero is eliminated and the range for negative numbers is increased by one.

Towards this end, we can rewrite the previous bit string inversion equations as:

V_{10}(Ā_{n}) = 2^{n} – [V_{10}(A_{n}) + 1] and

V_{10}(A_{n}) = 2^{n} –
[V_{10}(Ā_{n}) + 1]

The point is that to get the other member of a 2’s compliment pair, we must always invert the bit string and then add one. Note we can use the asterisk superscript, “*”, to indicate this computing the 2’s compliment pair. The inversion equations can then be more compactly displayed as follows:

** V _{10}(**

** **

** ****V _{10}(**

Mechanically, the way to get the other member of a 2’s compliment pair is to start from the right and invert every bit to the LEFT of the FIRST bit whose value is one.

In
2’s compliment notation, a bit string representing a positive number is
replaced by its 2’s compliment partner to give the corresponding negative
number. Consider the table of all possible 3-bit strings A_{3 }and a 2’s compliment function, Twos(A_{3})
which returns a decimal value:

Some interesting features of two’s compliment include

a) Zero is only represented once in the table and the range of negative values has been expanded by one.

b)
Positive 2’s compliment strings
always start with zero, i.e. the msb a_{n-1}=0 and

**Twos(A _{n}) = V(A_{n}) = 2^{n}**

c)
Negative 2’s compliment strings
always start with one, i.e. the msb a_{n-1}=1 and

**Twos(A _{n}) = V(A_{n}**

The
negative values run backwards in that the largest V(A_{n}) gives the
smallest Ones(A_{n}).

d)
The full range of values is **- ****2 ^{n-1}**

e)
The smallest negative number is -2^{n-1
}and there is NO positive analog. Inverting this value and adding one,
returns only the value from which we started. The difficulty is that the desired positive value is not expressible
given the constraint of “n” bits.

f)
The value for zero presents
another problem. Inverting zero and
adding one returns the value 2^{n. } This requires “n+1” bits to express and only gives
the desired string, i.e. of zero, if the final result is truncated to the
original “n” bits.

As a
consistency check, consider operations on the 2’s compliment of A_{3},
i.e. A_{3}^{*} = (Ā_{3}+1), for
all 3-bit strings as shown in the next table:

Note
that we somewhat arbitrarily choose values for the column, Twos( V(Ā_{3})+1 ), to correspond to the same bit pattern in the
argument, i.e. [ V(Ā_{3})+1 ], as
in the previous table. But more formally,

When
(a_{n-1})* = 0, Twos(A_{n}*) = V(A_{n}*) = V(Ā_{n}) +1 = 2^{n}
- V(A_{n}). And since a_{n-1 }=
1, Twos(A_{n}) = V(A_{n}) - 2^{n}.

Then

Twos(A_{n}*) = -Twos(A_{n}).

Likewise,
if (a_{n-1})* = 1, Twos(A_{n}*) = V(A_{n}*) - 2^{n }= V(Ā_{n}) +1 - 2^{n } =
-V(A_{n}). And since a_{n-1 }=
0, Twos(A_{n}) = V(A_{n}).

And so again, and for all values,

**Twos(****Ā**_{n}***)
= -Twos(****A**_{n}**).**

Basically, inverting the bit string and adding one, i.e. to get the 2’s compliment pair, multiplies the original 2’s compliment value by minus one.

**ARITHMETIC IN 2’s
COMPLIMENT**

1. Addition

The
addition of two “n-bit” numbers potentially results in an “n+1” bit quantity
and thus requires the sign extension of both numbers. Sign extension is really
only visible when the number is negative, i.e. the msb is one. Formally, to
add A_{n} and B_{n} we get

C[n:0]
= a_{n-1 * }2^{n} + V(A_{n}) + b_{n-1 * }2^{n}
+ V(B_{n})

C[n:0] = V( { a_{n-1,} a_{n-1}, a_{n-2},
…, a_{1}, a_{0} } } + V( { b_{n-1,} b_{n-1}, b_{n-2},
…, b_{1}, b_{0} } }

where the final result, C[n:0], is truncated to the smaller “n+1” bits, i.e. the “n+1” lsb-s.

Fast Look Ahead

Conditional MSB Pipes

2. Subtraction

The
subtraction of two n-bit numbers potentially results in an “n+1” bit quantity
and thus requires sign extension. Basically to subtract A_{n} from B_{n},
the exercise is to change the sign of A_{n} and then add. Formerly to
compute B_{n} minus A_{n }, we get,

C[n:0]
= b_{n-1 }(2^{n}) + V(B_{n}) - a_{n-1 }(2^{n})
- V(A_{n})

C[n:0]
= b_{n-1 }(2^{n}) + V(B_{n}) + ā_{n-1}(2^{n})
+ V(A_{n}*), where the asterisk “*” indicates a 2’s compliment pair

C[n:0] = b_{n-1 }(2^{n}) + V(B_{n})
+ ā_{n-1}(2^{n}) + V(Ā_{n}) + 1

C[n:0] = V_{2}( { b_{n-1,} b_{n-1},
b_{n-2}, …, b_{1}, b_{0} } ) + V_{2}( { ā_{n-1,
}ā_{n-1}, ā_{n-2}, …, ā_{2}, ā_{1}, ā_{0
}} ) + 1

3. Multiplication

The multiplication of two n-bit numbers potentially results in an “n+n = 2*n” bit quantity. Since multiplication is repeated addition, it is required that one of the numbers be positive. To multiply two negative numbers, one must be “effectively” changed to a positive number and thefinal result corrected at the end.

To multiply by a power of two, simply shift the 2’s compliment number to the left.

Booth Algorithm

Higher Radix Structures

Wallace Trees

4. Division

To divide by a power of two, simply shift the 2’s compliment number to the right while sign extending in the msb-s. The main problem is how to round especially for negative numbers. Please note the basic operation of division truncates to a smaller number, rather than rounding towards zero. This consistency is always to be preferred unless there is some unique frame of reference for the origin which is not generally the case in practice. If this reasonable advice is not heeded, then it is only necessary to add a (+1) to negative results to round towards zero.

EXAMPLE

Considering all possible 4 bit 2’s compliment numbers, division by four and two is easily accomplished by shifting to the right by two and by one respectively. Of course, negative numbers need to be sign-extended. The fraction that is discarded without rounding is indicated in parentheses.

Restoring and Non-Restoring Methods

High Radix Structures

5. Hardware Exponentiation

Successive Approximation

**RECOMMENDED READING**

- D.L. Fowler and J.E. Smith,
"An accurate, high speed implementation of division by reciprocal
approximation," in Proceedings of the 9
^{th}IEEE Symposium on Computer Arithmetic, Sep. 1989, pp. 60-67. - Hennessy & Patterson, "Computer Architecture: A Quantitative Approach," Appendix A (pp. A-2 to A-53), Morgan Kaufmann Publishers, Inc., 1990.
- A.D. Booth, "A signed binary multiplication technique," Quarterly Journal of Mechanics and Applied Mathematics, vol. 4, No. 22, pp. 236-240, 1951.