• ,/
There are 70 kinds of people in the world-those who understand
binary and those who don't.
?
-Anonymous
:~-
../ •••
.L
CHAPTER
Data Representation in
2 Computer Systems
==== 2.1
Thenumbers,
organization of any computer depends considerably on how it represents
characters, and control information. The converse is also true: Stan-
dards and conventions established over the years have determined certain aspects
of computer organization. This chapter describes the various ways in which com-
puters can store and manipulate numbers and characters. The ideas presented in
the following sections form the basis for understanding the organization and
function of all types of digital systems.
The most basic unit of information in a digital computer is called a bit, which
is a contraction of binary digit. In the concrete sense, a bit is nothing more than a
state of "on" or "off" (or "high" and "low") within a computer circuit. In 1964, the
designers of the IBM SystemJ360 mainframe computer established a convention
of using groups of 8 bits as the basic unit of addressable computer storage. They
called this collection of 8 bits a byte.
Computer words consist of two or more adjacent bytes that are sometimes
addressed and almost always are manipulated collectively. The word size repr~-
sents the data size that is handled most efficiently. by a particular architecture.
Words can be 16 bits, 32 bits, 64 bits, or any other size that makes sense within
the context of a computer's organization (including sizes that are not multiples of
eight). Eight-bit bytes can be divided into two 4-bit halves called nibbles (or
nybbles). Because each bit of a byte has a value within a positional numbering
system, the nibble containing the least-valued binary digit is called the low-order
nibble, and the other half the high-order nibble. ~
40 Chapter 2 / Data Representation in Computer Systems
2.2 POSITIONAL NUMBERING SYSTEMS
At some point during the middle of the sixteenth century, Europe embraced the
decimal (or base 10) numbering system that the Arabs and Hindus had been using
for nearly a millennium. Today, we take for granted that the number 243 means
two hundreds, plus four tens, plus three units. Notwithstanding the fact that zero
means "nothing," virtually everyone knows that there is a substantial difference
between having 1 of something and having 10 of something.
The general idea behind positional numbering systems is that a numeric value
is represented through increasing powers of a radix (or base). This is often
referred to as a weighted numbering system because each position is weighted
by a power of the radix.
The set of valid numerals for a positional numbering system is equal in size
to the radix of that system. For example, there are 10 digits in the decimal system,
o through 9, and 3 digits for the ternary (base 3) system, 0, 1, and 2. The largest
valid number in a radix system is one smaller than the radix, so 8 is not a valid
numeral in any radix system smaller than 9. To distinguish among numbers in dif-
. ferent radices, we use the radix as a subscript, such as in 3310 to represent the
decimal number 33. (In this book, numbers written without a subscript should be
assumed to be decimal.) Any decimal integer can be expressed exactly in any
other integral base system (see Example 2.1).
EXAMPLE 2.1 Three numbers represented as powers of a radix.
243.5110 = 2 X 102 + 4 X 101 + 3 X 100 + 5 X 10-1 + 1 X 10-2
2123 = 2 X 32 + 1 X 31 + 2 X 30 = 2310
101102 = 1 X 24 + 0 X 23 + 1 X 22 + 1 X 21 + 0 X 20 = 2210
The two most important radices in computer science are binary (base two), and
hexadecimal (base 16). Another radix of interest is octal (base 8). The binary sys-
tem uses only the digits 0 and 1; the octal system, 0 through 7. The hexadecimal
system allows the digits 0 through 9 with A, B, C, D, E, and F being used to rep-
resent the numbers 10 through 15. Table 2.1 shows some of the radices.
2.3 DECIMAL TO BINARY CONVERSIONS
Gottfried Leibniz (1646-1716) was the first to generalize the idea of the (posi-
tional) decimal system to other bases. Being a deeply spiritual person, Leibniz
attributed divine qualities to the binary system. He correlated the fact that any
integer could be represented by a series of ones and zeros with the idea that God
(1) created the universe out of nothing (0). Until the first binary digital computers
were built in the late 1940s, this system remained nothing more than a mathemat-
2.3 / Decimal to Binary Conversions 41
Powersot z Decimal 4-Bit Binary Hexadecimal
2-2 =!= 0.25 0 0000 0
2-1 =~= 0.5 1 0001 1
20 = 1 2 0010 2
21 = 2 3 0011 3
22 = 4 4 0100 4
23 = 8 5 0101 5
24 = 16 6 0110 6
25 = 32 7 0111 7
26 = 64 8 1000 8
27 = 128 9 1001 9
28 = 256 10 1010 A
29 = 512 11 1011 B
210 = 1,024 12 1100 C
215 = 32,768 13 1101 0
216 = 65,536 14 1110 E
15 1111 F
TABLE 2.1 Some Numbers to Remember
ical curiosity. Today, it lies at the heart of virtually every electronic device that
relies on digital controls.
Because of its simplicity, the binary numbering system translates easily into
electronic circuitry. It is also easy for humans to understand. Experienced com-
puter professionals can recognize smaller binary numbers (such as those shown in
Table 2.1) at a glance. Converting larger values and fractions, however, usually
requires a calculator or pencil and paper. Fortunately, the conversion techniques
are easy to master with a little practice. We show a few of the simpler techniques
in the sections that follow.
2.3.1 Converting Unsigned Whole Numbers
We begin with the base conversion of unsigned numbers. Conversion of signed
numbers (numbers that can be positive or negative) is more complex, and it is
important that you first understand the basic technique for conversion before con-
tinuing with signed numbers. .
Conversion between base systems can be done by using either repeated sub-
traction or a division-remainder method. The subtraction method is cumbersome
and requires a familiarity with the powers of the radix being used. Because it is
the more intuitive of the two methods, however, we will explain it first.
As an example, let's say that we want to convert 10410 to base 3. We know
that 34 = 81 is the highest power of 3 that is less than 104, so our base 3 number
will be 5 digits wide (one for each power of the radix: 0 through 4). We make
note that 81 goes once into 104 and subtract, leaving a difference of 23. We know
that the next power of 3, 33 = 27, is too large to subtract, so we' note the zero
. ~"·~I""lcYe_J:';":O. ~ •..,...~"'~ .••.•.:.!I-"' •••~ __
42 Chapter 2 / Data Representation in Computer Systems
"placeholder" and look for how many times 32 = 9 divides 23. We see that it goes
twice and subtract 18.We are left with 5 from which we subtract 31 = 3, leaving
2, which is 2 X 30. These steps are shown in Example 2.2.
EXAMPLE 2.2 Convert 10410 to base 3 using subtraction.
104
-81 = 34 X 1
23
-0 = 33 X 0
23
-18 = 32 X 2
5
-3 = 31 X 1
2
-2 = 30 X 2
o 10410 = 102123
The division-remainder method is faster and easier than the repeated subtraction
method. It employs the idea that successive divisions by the base are in fact suc-
cessive subtractions by powers of the base. The remainders that we get when we
sequentially divide by the base end up being the digits of the result, which are
read from bottom to top. This method is illustrated in Example 2.3.
EXAMPLE 2.3 Convert 10410 to base 3 using the division-remainder method.
3 1104 2 3 divides 10434 times with a remainder of 2
3 134 1 3 divides 34 11 times with a remainder of 1
3ill 2 3 divides 11 3 times with a remainder of 2
3 l1 0 3 divides 3 1 time with a remainder of 0
3 l!. 1 3 divides 1 0 times with a remainder of 1
o
Reading the remainders from bottom to top, we have: 10410 = 102123.
This method works with any base, and because of the simplicity of the calcula-
tions, it is particularly useful in converting from decimal to binary. Example 2.4
shows such a conversion.
5 "
2.3 / Decimal to Binary Conversions 43
EXAMPLE 2.4 Convert 14710to binary.
21147.1 2 divides 14773 times with a remainder of 1
2 173 1 2 divides 73 36 times with a remainder of 1
2136 0 .2 divides 36 18 times with a remainder of 0
2118 0 2 divides 18 9 times with a remainder of 0
2 L2 1 2 divides 9 4 times with a remainder of 1
2~ 0 2 divides 4 2 times with a remainder of 0
2 ~ 0 2 divides 2 1 time with a remainder of 0
2 U 1 2 divides 1 0 times with a remainder of 1
o
Reading the remainders from bottom to top, we have: 14710= 100100112,
A binary number with N bits can represent unsigned integers from 0 to 2N - 1.
For example, 4 bits can represent the decimal values 0 through 15, while 8 bits
can represent the values 0 through 255. The range of values that can be repre-
sented by a given number of bits is extremely important when doing arithmetic
operations on binary numbers. Consider a situation in which binary numbers are
4 bits in length, and we wish to add 11112 (1510)to 11112.We know that 15 plus
15 is 30, but 30 cannot be represented using only 4 bits. This is an example of a
condition known as overflow, which occurs in unsigned binary representation
when the result of an arithmetic operation is outside the range of allowable preci-
sion for the given number of bits. We address overflow in more detail when dis-
cussing signed numbers in Section 2.4.
2.3.2 Converting Fractions
Fractions in any base system can be approximated in any other base system using
negative powers of a radix. Radix points separate the integer part of a number
from its fractional part. In the decimal system, the radix point is called a decimal
point. Binary fractions have a binary point.
Fractions that contain repeating strings of digits to the right of the radix point
in one base may not necessarily have a repeating sequence of digits in another
base. For instance, 7j is a repeating decimal fraction, but in the ternary system it
terminates as 0.23 (2 X 3-1 = 2 X ~).
We can convert fractions between different bases using methods analogous to
the repeated subtraction and division-remainder methods for converting integers.
Example 2.5 shows how we can use repeated subtraction to convert a number
from decimal to base 5.
44 Chapter 2 / Data Representation in Computer Systems
EXAMPLE 2.5 Convert 0.430410 to base 5.
0.4304
- 0.4000 = 5-1 X 2
0.0304
- 0.0000 = 5-2 X 0 (A placeholder)
0.0304
- 0.0240 = 5-3 X '3
0.0064.
- 0.0064 = 5-4 X 4
0.0000
Reading from top to bottom, we find 0.430410 = 0.20345.
Because the remainder method works with positive powers of the radix for con-
version of integers, it stands to reason that we would use multiplication to convert
fractions, because they are expressed in negative powers of the radix. However,
instead of looking for remainders, as we did above, we use only the integer part
of the product after multiplication by the radix. The answer is read from top to
bottom instead of bottom to top. Example 2.6 illustrates the process.
EXAMPLE 2.6 Convert 0.430410 to base 5 .
.4304
X 5
2.1520 The integer part is 2. Omit from subsequent multiplication .
.1520
X 5
0.7600 The integer part is O. We'll need it as a placeholder .
.7600
X 5
3.8000 The integer part is 3. Omit from subsequent multiplication .
.8000
X 5
4.0000 The fractional part is now zero, so we are done.
Reading from top to bottom, we have 0.430410 = 0.20345.
This example was contrived so that the process would stop after a few steps.
Often things don't work out quite so evenly, and we end up with repeating frac-
tions. Most computer systems implement specialized rounding algorithms to pro-
2.3 / Decimal to Binary Conversions 45
vide a predictable degree of accuracy. For the sake of clarity, however, we will
simply discard (or truncate) our answer when the desired accuracy has been
achieved, as shown in Example 2.7.
EXAMPLE 2.7 Convert 0.3437510 to binary with 4 bits to the right of the
binary point.
.34375
X 2
0.68750 (Another placeholder)
.68750
X 2
1.37500
.37500
X 2
0.75000
.75000
X 2
1.50000 (This is our fourth bit. We will stop here.)
Reading from top to bottom, 0.3437510 = 0.01012 to four binary places.
The methods just described can be used to directly convert any number in any
base to any other base, say from base 4 to base 3 (as in Example 2.8). However,
in most cases, it is faster and more accurate to first convert to base 10 and then to
the desired base. One exception to this rule is when you are working between
bases that are powers of two, as you'll see in the next section.
EXAMPLE 2.8 Convert 31214 to base 3.
First, convert to decimal:
31214 = 3 X 43 + 1 X 42 + 2 X 41 + 1 X 4°
= 3 X 64 + 1 X 16 + 2 X 4 + 1 = 21710
Then convert to base 3:
3 1217 1
3~ o
3~ o
3~ 2
3~ 2
o We have 31214 = 220013.
