Describe the different number representations
Number Representations
Computers
are built using logic circuits that operate on information represented by two
valued electrical signals. We label the two values as 0 and 1; and we define
the amount of information represented by such a signal as a bit of information,
where bit stands for binary digit. The most natural way to represent a number
in a computer system is by a string of bits, called a binary number. A text
character can also be represented by a string of bits called a character code.
1.
Non-negative Integers
The
easiest numbers to represent are the non-negative integers. To see how this can
be done, recall how we represent number in. the decimal system. A number such
as 2034 is interpreted as:
2*103+0*102+3*10l÷4*100
But
there is nothing special with the base 10, so we can just as well use base 2.
In base 2, each digit value is either 0 or 1, which we can represent for
instance by false and true, respectively.
In
fact, we have already hinted at this possibility, since we usually write 0, and
1 instead of false and true.
All
the normal algorithms for decimal arithmetic have versions for binary
arithmetic, except that they are usually simpler.
2.
Negative Integers:
Things
are easy as long as we stick to non-negative integers. They become more complicated
when we want to represent negative integers as well.
In
binary arithmetic, we simply reserve one bit to determine the sign. In the
circuitry for addition, we would have one circuit for adding two numbers, and
another for subtracting two numbers. The combination of signs of the two inputs
would determine which circuit to use on the absolute values, as well as the
sign of the output..
While
this method works, it turns out that there is one that is much easier to deal
with by electronic circuits. This method is called the ‘two’s complement’
method. It turns out that with this method, we do not need a special circuit
for subtracting two numbers.
In
order to explain this method, we first show how it would work in decimal
arithmetic with infinite precision. Then we show how it works with binary
arithmetic, and finally how it works with finite precision.
3.
Infinite-Precision Ten’s Complement:
Imagine
the odometer of an automobile. It has a certain number of wheels, each with the
ten digits on it. When one wheel goes from 9 to 0, the wheel immediately to the
left of it, advances by one position. If that wheel already showed 9, it too
goes to 0 and advances the wheel to its left, etc. Suppose we run the car
backwards. Then the reverse happens, i.e. when a wheel goes from 0 to 9, the wheel
to its left decreases by one.
Now
suppose we have an odometer with an infinite number of wheels. We are going to
use this infinite odometer to represent all the integers.
When
all the wheels are 0, we interpret the value as the integer 0.
A
positive integer n is represented .by an odometer position obtained by
advancing the rightmost wheel a positions from 0. Notice that for each such
4.
Finite-Precision Ten’s Complement
Suppose
we have only a fixed number of wheels, say 3. In this case, we shall use the
convention that if the leftmost wheel shows a digit between
and
4 inclusive, then we have a positive number, equal to its representation. When
instead the leftmost wheel shows a digit between 5 and 9 inclusive, we have a negative
number, whose absolute value can be computed with the method that we have in
the previous section.
We
now assume that we have a circuit that can add positive three digit numbers,
and we shall see how we can use it to add negative numbers
our
representation.
Suppose
again we want to add -2 and +5. The representations for these numbers with
three wheels are 998 and 005 respectively. Our addition circuit will attempt to
add the two positive numbers 998 and 005, which gives 1003. But since the
addition circuit only has three digits, it will truncate the result to 003,
which is the right answer for our interpretation.
5.
Finite-Precision Two’s Complement:
So
far, we have studied the representation of negative numbers using ten’s
complement. In a computer, we prefer using base two rather than base ten.
Luckily, the exact method described in the previous section works just as well
for base two. For an n-bit adder (n is usually 32 or 64); we can represent
positive numbers with a leftmost digit of 0, which gives values between 0 and
2” - 1, and negative numbers with a leftmost digit of 1, which gives values
between -2 and -1.
The
exact same rule for overflow and underflow detection works. If, when adding two
positive numbers, we get a result that looks negative (i.e. with its leftmost
bit 1), then we have an overflow. Similarly, if, when adding two
negative
numbers, we get a result that looks positive (i.e. with its leftmost bit 0),
then we have an underflow.
6.
Rational Numbers:
Integers
are useful, but sometimes we need to compute with numbers that are not integer.
An
obvious idea is to use rational numbers. Many algorithms, such as the simplex
algorithm for linear optimization, use only rational arithmetic whenever the
input is rational.
There
is no particular difficulty in representing rational numbers in a computer. it
sufficed to have a pair of integers, one I or the numerator and one for the
denominator.
To
implement arithmetic on rational numbers, we can use some additional
restrictions on our representation. We may, for instance, decide that:
:•
positive rational numbers are always represented as two positive integers (the
other possibility is as two negative numbers),
a
negative rational numbers are always represented with a negative numerator and
a positive denominator (the other possibility is with a positive numerator and
a negative denominator),
•
the numerator and the denominator are always relative prime (they have no
common factors).