2. Data Representation
Part of
22C:40, Computer Organization and Hardware Notes
|
When we write computer programs, we always deal with representations. For example, we don't deal with text the way a calligrapher or author deals with text, we deal with a specific character set that may be used to represent text. Instead of dealing with integers or real numbers, we deal with finite precision representations of integers and we deal with floating point numbers.
Well designed programming languages allow the programmer to treat these representations as if they were identical to the abstractions they represent, but this identity is never complete. Thus, for example, our machine representations of integers behave exactly like abstract integers until a result greater than the machine precision is produced; at that point, either the behavior of integer variables becomes very strange (the usual consequence in C++) or the program raises an exception (the usual consequence in Java).
Just about every introduction to assembly language or machine language programming ever written begins with a section like this. The IBM 7040/7044 Data Processing System Student Text (IBM, 1963) begins with with a chapter on binary arithmetic that is as good as anything more recent, and the Introduction to Programming for the PDP-8 (DEC, 1973) has a nice "Number System Primer" that covers this ground equally well!
All modern computers use binary representations for their data, and all use fixed size containers for data. There is no reason that computers could not be built that use other basic representations; "trinary" (base 3) logic devices aren't hard to build, and in fact, decimal computers were built in large numbers in the 1960's. There is no compelling benefit to using non-binary representations, though, and even the decimal machines of the 1960's were built using binary logic and used binary-coded-decimal (BCD) internally.
The bit is the fundamental unit of information. A bit has two values, conventionally called zero or one. We could as easily name the values on and off, high and low, or true and false; in fact, all of those names are used in different contexts, and the truth is that all such names are arbitrary!
Over the past 50 years, bits have been grouped inside computers in many ways, and these groupings have been given many names:
How many values can be coded in one bit? Two! We'll call them 0 and 1 for now. How many values can be coded by 2 bits? By 3 bits? By 4 bits? Here is a systematic listing of all possible combinations of 4 bits:
0 0 0 0 | 1 0 0 0 | 4 bits, 24 = 16 possibilities |
0 0 0 1 | 1 0 0 1 | |
0 0 1 0 | 1 0 1 0 | |
0 0 1 1 | 1 0 1 1 | |
0 1 0 0 | 1 1 0 0 | |
0 1 0 1 | 1 1 0 1 | |
0 1 1 0 | 1 1 1 0 | |
0 1 1 1 | 1 1 1 1 |
In general, to get n combinations, you need log2(n) bits (log2 is the logarithm to the base 2), rounded up to the nearest integer, since it is hard to physically represent a fractional bit.
How we chose to associate values with these bits is our business! We could decide that 0000 means Tuesday and 0001 means five, if we wanted, and, in fact, character sets frequently look that arbitrary! Consider the character set used by ILLIAC I, a computer built at the University of Illinois in the 1940's; the table below was transcribed from a typewritten original in The ILLIAC Miniature Manual by John Halton (U. of Illinois Digital Computer Lab file no 260, Oct 22 1958, page 3):
| Characters |n for 92 Tape Holes | F/S L/S | Orders ----------------------------------- o 0 P 2F o O 1 Q 66F o O 2 W 130F o OO 3 E 194F oO 4 R 258F oO O 5 T 322F oOO 6 Y 386F oOOO 7 U 450F Oo 8 I 514F Oo O 9 O 578F Oo O + K 642F Oo OO - S 706F OoO N N 770F OoO O J J 834F OoOO F F 898F OoOOO L L 962F O o Delay Delay 3F O o O $(Tab) D 67F O o O CR/LF CR/LF 131F O o OO ( B 195F O oO L/S=Letter-Shift 259F O oO O , V 323F O oOO ) A 387F O oOOO / X 451F OOo Delay Delay 515F OOo O = G 579F OOo O . M 643F OOo OO F/S=Figure-Shift 707F OOoO ' H 771F OOoO O : C 835F OOoOO x Z 899F OOoOOO Space Space 963F |
This character set is coded in 5 bits, with L/S and F/S as shift codes for switching between two different and wildly disorganized sets of 32 characters! How the designers of this character set decided on the order of the letters is a mystery! Note that the capital O in the "tape holes" column stands for the digit one in the binary code, while blank stands for the digit zero. The lower case o in the "tape holes" column shows where the sprocket hole in the tape goes; this is not part of the binary code, and is more like a decimal point, from the human reader's perspective.
Exercises:
a) Show the representation for the string "HELLO WORLD." as it would have appeared punched on paper tape for the ILLIAC I. Remember, the initial state of the teletype is unknown! You don't know if the previous text left it set in figure-shift or letter-shift state. (Use upper-case O for holes in tyhe tape, and a lower-case o for the sprocket hole.)
b) Show the sequence of 5-bit binary values corresponding to the string "HELLO WORLD." for the ILLIAC I.
The modern ISO/7 or ASCII character set, originally proposed in the early 1960's, is a significant improvement:
left 3 bits | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|
000 | 001 | 010 | 011 | 100 | 101 | 110 | 111 | |||
Right 4 bits | 0000 | NUL | DLE | SP | 0 | @ | P | ` | p | |
0001 | SOH | DC1 | ! | 1 | A | Q | a | q | ||
0010 | STX | DC2 | " | 2 | B | R | b | r | ||
0011 | ETX | DC3 | # | 3 | C | S | c | s | ||
0100 | EOT | DC4 | $ | 4 | D | T | d | t | ||
0101 | ENQ | NAK | % | 5 | E | U | e | u | ||
0110 | ACK | SYN | & | 6 | F | V | f | v | ||
0111 | BEL | ETB | ' | 7 | G | W | g | w | ||
1000 | BS | CAN | ( | 8 | H | X | h | x | ||
1001 | HT | EM | ) | 9 | I | Y | i | y | ||
1010 | LF | SUB | * | : | J | Z | j | z | ||
1011 | VT | ESC | + | ; | K | [ | k | { | ||
1100 | FF | FS | , | < | L | \ | l | | | ||
1101 | CR | GS | - | = | M | ] | m | } | ||
1110 | SO | RS | . | > | N | ^ | n | ~ | ||
1111 | SI | US | / | ? | O | _ | o | DEL |
In the ASCII code, for example, the string "Hello World!" would be represented as:
1001000 | H | ||
1100101 | e | ||
1101100 | l | ||
1101100 | l | ||
1101111 | o | ||
0100000 | |||
1010111 | W | ||
1101111 | o | ||
1110010 | r | ||
1101100 | l | ||
1100100 | d | ||
0100001 | ! |
The ASCII character set, now officially known as the ISO/7 character set, is the basis of all of the widely used character sets in common use today. From the very start, ASCII text has been encoded in 8 bit bytes by adding an extra bit on the left, so the letter 'a' is coded as 01100001 instead of being coded as 1100001. Modern 8-bit character sets use this extra bit to allow for additional characters.
One other character set from the "bad old days" is still with us, EBCDIC, an 8-bit character set originally devised by IBM in the 1960s.
Note that the ancient ILLIAC character set and ASCII both contain a number of codes that are not intended as printable characters. In ASCII, and for that matter, in EBCDIC, these have standard 2 and 3 letter names. Except for space, with the printable name SP, these special characters are known as control characters. Here are the meanings of the control characters used in ASCII:
NUL | null, intended to be ignored, abused as end-of-string | |
---|---|---|
SOH | start of heading | |
STX | start of text | |
ETX | end of of text | |
EOT | end of of transmission | |
ENQ | enquire (about the status of a remote terminal?) | |
ACK | acknowledge (an answer to ENQ?) | |
BEL | \b | bell, used to ring the bell in the remote terminal |
BS | backspace | |
HT | \t | horizontal tab |
VT | vertiacal tab | |
LF | \n | linefeed, frequently used as end-of-line |
FF | \f | formfeed (eject page from printer) |
CR | \r | carriage return, frequently used to mean enter |
SO | shift out | |
SI | shift in | |
DLE | data link escape | |
DC1 | device control 1 | |
DC2 | device control 2 | |
DC3 | device control 3 | |
DC4 | device control 4 | |
NAK | negative acknowledge (an answer to ACK?) | |
SYN | synchronize | |
ETB | end transmission block | |
CAN | cancel | |
EM | end of message | |
SUB | substitute | |
ESC | escape | |
FS | file separator | |
GS | group separator | |
RS | record separator | |
US | unit separator | |
SP | space | |
DEL | delete, intended to be ignored |
Exercises:
c) Show the representation for the string "HELLO WORLD." in 7-bit ASCII, as a sequence of binary numbers.
It is possible to associate arbitrary bit patterns with numeric values, so nothing, in theory, prevents us from deciding to represent zero as 1101 and one 1000, for example, but using such a mapping from binary values to the integers makes arithmetic extremely difficult -- in effect, this arbitrary mapping forces us to use table-lookup schemes for all arithmetic operations.
Table lookup has been used as the basis of all arithmetic on at least one computer, the IBM 1620, codenamed the Cadet during development in the late 1950's. Later, someone decided that the name should be interpreted as an acronym, for "Can't Add, Doesn't Even Try," because the machine used table lookup to compute the results of all arithmetic operations. Some programmers even loaded new tables in this machine so that they could do arithmetic in bases other than 10, the base for which the machine was designed.
With few exceptions, all computers today use variations on the binary number system for arithmetic. The basic binary number system we use today dates back to ancient China, where it was used to order of the 64 combinations of I-Ching sticks (each stick could be in either of two states; the pattern that resulted from a throw of the sticks was used for fortune telling):
0 | = | 000000 | 16 | = | 010000 | 32 | = | 100000 | 48 | = | 110000 | |||
1 | = | 000001 | 17 | = | 010001 | 33 | = | 100001 | 49 | = | 110001 | |||
2 | = | 000010 | 18 | = | 010010 | 34 | = | 100010 | 50 | = | 110010 | |||
3 | = | 000011 | 19 | = | 010011 | 35 | = | 100011 | 51 | = | 110011 | |||
4 | = | 000100 | 20 | = | 010100 | 36 | = | 100100 | 52 | = | 110100 | |||
5 | = | 000101 | 21 | = | 010101 | 37 | = | 100101 | 53 | = | 110101 | |||
6 | = | 000110 | 22 | = | 010110 | 38 | = | 100110 | 54 | = | 110110 | |||
7 | = | 000111 | 23 | = | 010111 | 39 | = | 100111 | 55 | = | 110111 | |||
8 | = | 001000 | 24 | = | 011000 | 40 | = | 101000 | 56 | = | 111000 | |||
9 | = | 001001 | 25 | = | 011001 | 41 | = | 101001 | 57 | = | 111001 | |||
10 | = | 001010 | 26 | = | 011010 | 42 | = | 101010 | 58 | = | 111010 | |||
11 | = | 001011 | 27 | = | 011011 | 43 | = | 101011 | 59 | = | 111011 | |||
12 | = | 001100 | 28 | = | 011100 | 44 | = | 101100 | 50 | = | 111100 | |||
13 | = | 001101 | 29 | = | 011101 | 45 | = | 101101 | 61 | = | 111101 | |||
14 | = | 001110 | 30 | = | 011110 | 46 | = | 101110 | 62 | = | 111110 | |||
15 | = | 001111 | 31 | = | 011111 | 47 | = | 101111 | 63 | = | 111111 |
In looking formally at how the bit pattern for a number is related to its abstract value, we must distinguish clearly between representation and abstraction. Conventionally, when we say "ten" we are using the name of an abstract value, without any reference to number systems. We have such simple names for all values up to 12. When we write "12", however, we are using a decimal representation of the abstract value denoted by the name "twelve".
In what follows, we will use a programming language notation, where unquoted numerals stand for abstract integer values, subject to arithmetic operations, while quoted strings stand for concrete representations of those values.
Thus, the string "011100" is just a string of symbols, with no inherent meaning. It could be equivalent to "eleven thousand one hundred" if we decided to interpret it as a decimal number, or it could be the binary representation of the number 28.
Consider, first, the formula that relates representations of decimal numbers to their values:
i=digits(S)-1 | ||
value(S) = | v(S[i]) × 10i (decimal) | |
i = 0 |
Users of the decimal system rarely use mathematical notation, as above; instead, we speak of the one's place, the ten's place, the hundred's place and so on.
The formula given above can be directly reduced to code in a high level programming language! For example, the following C code will convert from decimal numbers, passed as a string, to the corresponding binary value, encoded in a variable of type int:
int value( char S[] ) { int i; int a = 0; for (i = 0; i < strlen(S); i++) { a = a + v[S[i]] * (int)pow( 10, i ); } return a; }
This function converts decimal to binary because it assumes that the representation of all values of type int is binary, and it assumes that the computer performing this computation is a binary computer! This function is awful, for a number of reasons: First, it uses floating point arithmetic to compute 10i on each iteration, when it could have simply multiplied the previous multiplier by 10. Second, it uses a table to find the integer values each digit in the string, when there are much faster ways of doing this. Third, it computes the length of the string over again on each iteration of the loop, and finally, and most importantly from the point of view of human users, the digits in the string are interpreted backwards, so the least significant digit, or the one's place, is the first character in the string. Conventional renderings in the Roman character set with left-to-right printing would have us put the most significant digit first.
Exercises:
d) Convert the above function to the language of your choice and write a small program to try it out on some real strings of digits, giving as output the string it converted and the value of that string.
e) Fix the code you just wrote so it avoids re-evaluating the string-length with each iteration.
f) Fix the code you just wrote so it avoids using an exponential function, but instead starts with a multiplier of 1 and multiplies this by 10 on each iteration.
g) Fix the code you just wrote so it evaluates the digits of the number in their conventional order.
The formula given above applies equally well for computing the abstract value of a binary number, with the simple restriction that each binary digit, or bit may take on only two values, 0 and 1, and that the base of the number system is 2 instead of 10:
i=digits(S)-1 | ||
value(S) = | v(S[i]) × 2i (binary) | |
i = 0 |
If we evaluate this formula using decimal arithmetic, as we would typically do with pencil and paper, it is an excellent formula for converting from decimal to binary!
Similarly, in binary numbers, we speak of the one's place, the two's place, the four's place and the eight's place. The list of powers of 2 rapidly becomes familiar to users of binary numbers:
i | 2i | |
---|---|---|
0 | 1 | |
1 | 2 | |
2 | 4 | |
3 | 8 | |
4 | 16 | |
5 | 32 | |
6 | 64 | |
7 | 128 | |
8 | 256 | |
9 | 512 | |
10 | 1024 | =~ 1,000 = 1K (kilo) |
11 | 2048 | |
12 | 4096 | |
13 | 8192 | |
14 | 16382 | |
15 | 32768 | |
16 | 65536 | |
20 | 1048576 | =~ 1,000,000 = 1M (mega) |
30 | =~ 1,000,000,000 = 1G (giga) | |
40 | =~ 1,000,000,000,000 = 1T (tera) |
Note that each power of two is twice the previous power of two, and note the convenient coincidence that 210, 1024, is very close to 103, 1000. This allows quick estimates of the magnitude of binary numbers -- if you have a binary number with 10 bits, it's close to a thousand, while if it has 20 bits, it could be close to a million.
Exercises:
h) What is 224? Several machines were once built with 24-bit words.
i) What is 232, in decimal, exactly. This is relevant on machines with a 32-bit word!
j) The maximum integer that can be represented with a 6-bit binary value is 63 while 26 is 64. The maximum integer that can be represented with a 2-digit decimal value is 99 while 102 is 100. What is the maximum integer than can be represented in n-bits, as a function of n?
To convert binary to decimal using pencil and paper, just write the place values over each bit position, in decimal, and then sum the products of the place values times the digits under them. For binary numbers, these products are either zero or the place value itself, since the multiplier is either zero or one, so the arithmetic is simple. For example, to find the decimal equivalent of 101010112 we proceed as follows:
128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 |
101010112 = 128+32+8+2+1 = 171
To convert a decimal number to binary using pencil and paper, divide the number by two, writing the integer part of the quotient below the number and writing the remainder off to the side. Repeat this process until you reach a quotient of zero, and the column of remainders you are left with, off to the side, will be the binary number if you read it from bottom to top. So, to convert 171 to binary, we proceed as follows:
171 | ||
85 | 1 | |
42 | 1 | |
21 | 0 | |
10 | 1 | |
5 | 0 | |
2 | 1 | |
1 | 0 | |
0 | 1 | 101010112 |
The above two exercises confirm each other since the final result of converting to decimal and then back to binary is the same as the original value.
Exercises:
k) Flip a coin 8 times, in sequence, and write down 1 for each time it comes up heads, and 0 for each time it comes up tails in order to make an 8-bit binary number. Convert that to decimal. Convert the result back to binary to check your work!
l) Write a little program that takes as input an integer and prints that integer converted to that number base. Note that in C, C++ and Java, the for positive integer operands, the / and % operators return the quotient and remainder.
How do we relate the characters used to represent digits to their abstract numeric values? When working with pencil and paper, we did this using rules learned in elementary school, and it may have seemed so natural that it passed unnoticed. When working on a computer, however, this problem poses minor difficulties. The most general solution to this problem is to use some kind of table, for example, consider a table indexed by the ASCII value of the character and used to recover the integer value of the digit:
int v(char d) { static values[128] = { 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,1,2,3, 4,5,6,7, 8,9,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0 } return values[d]; }
This is computationally fast, but there is really no need for to use array indexing here! The reason is that almost all character codes that have ever been used on computers have assigned consecutive values, in the character code, to the symbols for the digits. This was true even with the quirky character set used on ILLIAC! As a result, the following works:
int v(char d) { return d - '0'; }The above code is legal C and C++, and very similar code is legal in Java and C#. The one thing to notice is that, in languages descended from C, variables of type character and integer are really members of the same abstract type, with integer values. In many other languages, strong type checking prevents integers and characters from being mixed in expressions, so explicit conversions must be used to get the integer values used to represent some character or the character value represented by some integer. As an example, consider this little bit of Pascal code that is exactly equivalent to the C code given above:
function v(d: char): integer; begin v = int(d) - int('0'); end;In Pascal, the special function int() asks for the integer used to represent some character -- it is not really a function, just instructions to the compiler to take the binary code that was used to represent the character and treat it as an integer -- something C and C++ do without being told. The equivalence between the above Pascal and C code is so total that it is likely that Pascal compiler would produce the exact same machine code for this function as a C compiler.
Any integer may be used as the radix of a number system. The formula used above to evaluate numbers in bases 2 and 10 also works for r, an arbitrary radix:
i=digits(S)-1 | ||
value(S) = | v(S[i]) × ri (radix r) | |
i = 0 |
Note that, for any radix r, the string "10" in that radix has, as its value, the radix. Thus, in binary, 10 means two, in decimal, the string 10 means ten, and in octal, the string 10 means eight. To avoid confusion, it is conventional to indicate the number base by a numerical subscript, as
101102 = 268 = 2210 = 2113
As long as the radix r is no greater than 10, the conventional digits, 0 through 9, can be used. For r greater than 10, additional symbols must be chosen for use as digits. Historically, a variety of symbols have been used! For example, in base 12 also called duodecimal, the digits T and E have been used (T for ten and E for eleven). Later, on ILLIAC I, the following digits were used for base 16, which the ILLIAC I documentation called the sexadecimal number system:
0123456789KSNJFL
Today, the standard convention for bases greater than ten is to use A for ten, B for eleven, C for twelve, and so on, up to Z. This allows for bases as high as 36, although the highest commonly used number base is base 16, usually called hexadecimal, using the digits.
0123456789ABCDEF
In the context of computer systems based on binary numbers, it is common to use bases 8 and 16. The reason for this is that it is generally easier for people to treat very long numbers in terms of groups of digits. For example, in dealing with large decimal numbers, we group the digits in threes. In effect, this grouping for decimal numbers creates a number in base 1000 with three character names for each digit in that number and commas separating the digits. Consider the representation of 1000 in binary:
1000 = 512 + 256 + 128 + 64 + 32 + 8
100010 = 11111010002
The problem with this number is that it is long, and just as we prefer to group digits of long decimal numbers into groups for readability, we also prefer to group the bits of long binary numbers into groups for readability. If we group the bits in groups of 3, we can treat each triplet of bits as an octal (base 8) digit, and if we group the digits in groups of 4, we can treat each group of bits as a hexadecimal digit:
100010 = 1,111,101,0002 = 17508
100010 = 11,1110,10002 = 3E816
Note that, for integers, we always group digits from the least significant end of the number, leaving the odd leftovers for the most significant bits of the number. This is exactly the same grouping rule we routinely use with decimal integers.
The pencil and paper conversion algorithms given for binary values actually work for any place-value number system. To convert to decimal, given a number in base r, write successive powers of r over successive digits, starting with 1 over the least significant digit, and then multiply each digit by the power of r above it and sum the products. To convert a decimal number to base r, divide it repeatedly by r, setting aside the remainders, until you get zero, and then write the remainders in order, last to first, as successive digits of the number.
Exercises:
m) Given the numbers 1b, 10b, 100b and 1000b, where b is the unknown number base, what are the decimal equivalents for these numbers, assuming that the base is 2? Assuming that it is 8? Assuming that it is 10?
n) The letters A through F are sufficient to spell many words, and we can augment them with misreadings of the digits 0 and 1 as the capital letters O and I to spell even more words. So, what decimal value, when converted to hexadecimal, spells the words BEEF, FEED, FOOD, and CODE? What are the corresponding binary values? What are the corresponding octal values?
o) Flip a coin 8 times, in sequence, and write down 1 for each time it comes up heads, and 0 for each time it comes up tails in order to make an 8-bit binary number. Convert that to decimal. Convert the result to octal, and then replace each digit by it's 3-bit binary representation. You should get your original number back.
p) Flip a coin 8 times, in sequence, and write down 1 for each time it comes up heads, and 0 for each time it comes up tails in order to make an 8-bit binary number. Convert that to decimal. Convert the result to hexadecimal, and then replace each digit by it's 4-bit binary representation. You should get your original number back.
It is common, in the modern world, to hear that some nuclear weapon has an explosive yield equivalent to so many megatons, or that a disk has a capacity of so many gigabytes, or that a computer has so many megabytes of main memory. Units of measurement like the kilometer and the millimeter are also widely used. It is important to remember that the multipliers used for such units, multipliers like kilo- and milli-, have precise meanings that are defined by international standards as part of the SI system of measurement, otherwise known as the metric system:
1T | = | 1 | tera | = | 1,000,000,000,000 | |
1G | = | 1 | giga | = | 1,000,000,000 | |
1M | = | 1 | mega | = | 1,000,000 | |
1K | = | 1 | kilo | = | 1,000 | |
1 | = | 1 | = | 1 | ||
1m | = | 1 | milli | = | .001 | |
1µ | = | 1 | micro | = | .000,001 | |
1n | = | 1 | nano | = | .000,000,001 | |
1p | = | 1 | pico | = | .000,000,000,001 |
In the world of computers, we have on-line disk subsystems with capacities measured in terabytes, or Tbytes, and we have CPU clock speeds measured in gigahertz or GHz. Small microcontrollers have memory capacities measured in kilobytes or Kbytes, and data communications lines may have lengths measured in kilometers or Km. We also have memory speeds measured in nanoseconds or ns, chip sizes measured in square millimeters or mm, and we have disk access times measured in milliseconds, ms. Note that capitalization is used to indicate whether the multiplier is greater than or less than one, and note the use of the Greek letter mu, µ, used for microseconds. The speed of light is remarkably close to one foot per nanosecond.
When someone tells you that their memory has a capacity of 100Kb, unfortunately, you are in trouble. Chip designers will tend to use this to refer to kilobits or Kbits, while computer system designers will expect it to stand for kilobytes or Kbytes. As a rule, spell it out if there is any doubt!
In the world of computer science, it is common to use one K or one kilo to refer to a multiplier is 1024, but in fact, this usage is only approximate. In the world of disks, it is common to use strange mixed approximations, where mega means 1000×1024. To distinguish multipliers that are powers of 2 from multipliers that are powers of 10, it has been suggested that we should use the subscript 2 to indicate the common computer science approximation, while reserving the unsubscripted form for the exact SI prefix.
1 kilo2 = 1024
1 mega2 = 1,048,576
Of course, this leaves us with no convenient notation for the disk salesman's definition of a megabyte as 1000 times 1024. Fortunately, this absurd usage is in decline.
Exercises:
q) How long is a microfortnight, in seconds.
r) How heavy is a kilodram (weight), in pounds? How heavy is a megadram in tons? (Be careful to use the definition of a dram as a unit of weight, because it is also defined as a unit of volume.)
On computers, we generally are forced to work in terms of a fixed word size, so our numbers are composed of a fixed number of bits. Leading zeros are used to pad a number out to the desired width. Thus, on a machine with a 16 bit word,
10010 = 0000,0000,0110,01002 = 006416
On this machine, the maximum representable number is
6553510 = 1111,1111,1111,11112 = FFFF16
When deciding between octal and hexadecimal for compact representation of numbers, it is common to select one that divides words and bytes evenly, so for machines based on an 8 bit byte, hexadecimal seems a good choice, while for machines with a 6 bit byte, octal makes sense.
There are exceptions to this! The Motorola 68000 and its predecessor, the DEC PDP-11, are essentially 16 bit machines with 8 bit bytes, but the instruction format is made of numerous 3 bit fields, so displaying 68000 or PDP-11 instructions in octal makes very good sense! The old Intel 8080, similarly, had an 8-bit instruction byte that was divided into a 2-bit field followed by two 3-bit fields, so again, it was convenient to print the contents of memory in octal. The Unix system and the C programming language were first implemented on the PDP-11 system, so to this day, Unix and C make it very easy to use octal, while supporting hexadecimal as something of an afterthought.
Recall that the value of a simple binary number, represented as a string S of digit symbols, is defined as:
i=digits(S)-1 | ||
value(S) = | v(S[i]) × 2i | |
i = 0 |
It should not be surprising, then, that binary arithmetic strongly resembles decimal arithmetic. To add two decimal numbers, for example, to add 132 to 39, we arrange the numbers as follows:
1 | 3 | 2 | augend | ||
+ | 3 | 9 | addend | ||
|
And then do the addition one pair of digits at a time, starting with 2+9. To add one pair of digits, we use an addition table that most of us should have memorized in elementary school:
+ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
---|---|---|---|---|---|---|---|---|---|---|---|
0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
2 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
3 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | |
4 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | |
5 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | |
6 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | |
7 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | |
8 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | |
9 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | |
10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
For the example, looking up 2+9 in the table gives a sum of 11; we split this sum into two pieces, the sum digit and the carry digit, writing the result as follows:
1 | carry | ||||
1 | 3 | 2 | augend | ||
+ | 3 | 9 | addend | ||
| |||||
1 | sum |
In adding up the digits in the next column, we face a small problem: There are three numbers in this column, but our addition table only allows for the addition of two digits. There are many ways to solve this problem. One is to use the same addition table, with the augend as the column index and the addend as the row index, but use the row below the indexed row. This explains the extra row in the above table! Adding the carry to the addend before using the table or adding the carry to the table entry both produce the same result. Doing this to solves the 1+3+3 problem in the 10's place of our example gives 7 and no carry, so we write this into our work:
1 | carry | ||||
1 | 3 | 2 | augend | ||
+ | 3 | 9 | addend | ||
| |||||
7 | 1 | sum |
Finally, we solve the trivial problem of the most significant digits of the addend where there were no carries by simply copying them down, giving the final sum:
1 | carry | ||||
1 | 3 | 2 | augend | ||
+ | 3 | 9 | addend | ||
| |||||
1 | 7 | 1 | sum |
Binary addition can be done using exactly the approach described above, but substituting the following much smaller table for the addition table:
  | + | 0 | 1 | ||
---|---|---|---|---|---|
0 | 0 | 1 | |||
1 | 1 | 10 | |||
10 | 11 |
If this seems too simple, it is because it really is that simple! All the rules are the same as for decimal arithmetic because the place-value system is the same system. The only change is a reduction in the number of values each digit can take on. This means that remembering things like the addition and multiplication tables is far easier in binary than in decimal. The penalty we pay is that, in any arithmetic problem, we have more digits to deal with. To represent quantities that would be comfortably represented in 1 decimal digit, it takes 4 binary digits. To represent a 3 decimal digit quantity takes 10 binary digits. Converting decimal to binary, adding the binary numbers using the above rules, and converting the binary sum back to decimal gives:
decimal | binary | ||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | carry | 1 | |||||||||||||||
1 | 3 | 2 | augend | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | ||||||
+ | 3 | 9 | addend | + | 1 | 0 | 0 | 1 | 1 | 1 | |||||||
| | ||||||||||||||||
1 | 7 | 1 | sum | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 |
Not surprisingly, the sum is the same!
If there is a limit on the number of bits allowed, as on a computer with a fixed word size, we say that an overflow has occurred if the carry out of the topmost bit of our fixed size word is nonzero. Note that this applies to words used to hold unsigned data, and that the conventions for detecting overflow are more complex if we are interested in also representing negative numbers.
Exercises:
s) Flip a coin 16 times to produce 2 8-bit binary numbers. Add them in binary, and then convert the original numbers to decimal, add them, and convert the result back to binary in order to check your sum.
Subtraction in binary is as easy as subtraction in decimal. Borrowing follows the same rules in binary and decimal, but binary subtraction involves more digits and far simpler details at each digit. Subtraction, however, introduces the problem of negative numbers, and these are not usually represented in computers in the same way that we represent them on paper!
Consider the problem of representing positive and negative numbers using 4 bits for each number. One way to do this is to follow our intuition from the world of pencil and paper and simply reserve one bit to represent the sign while the remaining bits are used to hold the conventional binary representation of the magnitude. This is called the signed magnitude number system With such numbers, we can think of the sign bit as taking on the values + and -, while the 3 magnitude bits take on the values 0 and 1 and follow a place-value system of interpretation. This allows the representation of the following 16 values:
0 | 0 | 0 | 0 | +0 | 1 | 0 | 0 | 0 | -0 | |||
0 | 0 | 0 | 1 | +1 | 1 | 0 | 0 | 1 | -1 | |||
0 | 0 | 1 | 0 | +2 | 1 | 0 | 1 | 0 | -2 | |||
0 | 0 | 1 | 1 | +3 | 1 | 0 | 1 | 1 | -3 | |||
0 | 1 | 0 | 0 | +4 | 1 | 1 | 0 | 0 | -4 | |||
0 | 1 | 0 | 1 | +5 | 1 | 1 | 0 | 1 | -5 | |||
0 | 1 | 1 | 0 | +6 | 1 | 1 | 1 | 0 | -6 | |||
0 | 1 | 1 | 1 | +7 | 1 | 1 | 1 | 1 | -7 |
The signed magnitude system works, and in the sense that representation systems are, ultimately, arbitrary, it is as good as any other number system. Many early binary computers used this number system, and this system still sees some use in special circumstances. It turns out, however, that it is easier to build arithmetic hardware for other systems of signed numbers, so the signed magnitude system is not commonly used for integer arithmetic on modern computers.
Signed magnitude numbers do pose one annoyance because there are two values for zero, one positive and one negative. This is annoying because it would be nice to have the rule that two numbers are equal if and only if their representations are equal, and this is not the case here because +0 and -0 have different representations but the same abstract value.
To negate a signed magnitude number, all you need to do is flip the most significant bit from a one to a zero or from a zero to a one. On the other hand, to add two signed magnitude numbers, you must either add or subtract the magnitudes, depending on whether the signs are equal or unequal, and then set the sign of the result according to a rather complex set of rules.
An alternative way to make negative numbers is to arrange things so that the negative of a number is obtained by reversing all the bits of the corresponding positive number. This leads to the one's complement number system, illustrated with the following table of 4-bit signed numbers:
0 | 0 | 0 | 0 | +0 | 1 | 0 | 0 | 0 | -7 | |||
0 | 0 | 0 | 1 | +1 | 1 | 0 | 0 | 1 | -6 | |||
0 | 0 | 1 | 0 | +2 | 1 | 0 | 1 | 0 | -5 | |||
0 | 0 | 1 | 1 | +3 | 1 | 0 | 1 | 1 | -4 | |||
0 | 1 | 0 | 0 | +4 | 1 | 1 | 0 | 0 | -3 | |||
0 | 1 | 0 | 1 | +5 | 1 | 1 | 0 | 1 | -2 | |||
0 | 1 | 1 | 0 | +6 | 1 | 1 | 1 | 0 | -1 | |||
0 | 1 | 1 | 1 | +7 | 1 | 1 | 1 | 1 | -0 |
The operation of negating a one's complement number is called taking the one's complement of a number or one's complementing the number. So, the one's complement of 0000 is 1111 and the one's complement of 1111 is 0000. Note that negating a negative number produces a positive number, and visa versa. Also note that the one's complement operator is well defined even when other number systems are being used. The operator is defined in terms of its effect on the binary representation, not in terms of the interpretation of that representation.
Warning: Many students get confused by the use of the term one's complement to mean both the name of the number system and the name of the operator used to negate numbers in that system! If someone says: "Take the one's complement of x," or "one's complement x" that means to apply the operator, reversing each bit in x; the number of bits in the result will be the same as the number of bits in x. If someone says: "write x as a 4-bit one's complement number," that means to use the number system!
As was noted above, adding two signed magnitude numbers is fairly difficult. In contrast, the rules for adding two one's complement numbers are simple: Treat the most significant bit exactly like all the other bits, and compute the simple binary sum of the two numbers. Then, if this sum produces a carry out of the topmost bit, add one to the result!
This rule for addition is so simple that, when building computer hardware to do signed magnitude arithmetic, subtraction is always done by adding the one's complement of the number to be subtracted. One's complement has been used as the primary representation for integers on a number of computers, but almost all of these were designed prior to 1965.
Note that one's complement numbers and signed magnitude numbers share the problem with there beign two representations of zero, +0 and -0. This is eliminated when two's complement numbers are used. In the two's complement system, numbers are negated by taking the one's complement and then adding one.
0 | 0 | 0 | 0 | +0 | 1 | 0 | 0 | 0 | -8 | |||
0 | 0 | 0 | 1 | +1 | 1 | 0 | 0 | 1 | -7 | |||
0 | 0 | 1 | 0 | +2 | 1 | 0 | 1 | 0 | -6 | |||
0 | 0 | 1 | 1 | +3 | 1 | 0 | 1 | 1 | -5 | |||
0 | 1 | 0 | 0 | +4 | 1 | 1 | 0 | 1 | -3 | |||
0 | 1 | 0 | 1 | +5 | 1 | 1 | 0 | 1 | -3 | |||
0 | 1 | 1 | 0 | +6 | 1 | 1 | 1 | 0 | -2 | |||
0 | 1 | 1 | 1 | +7 | 1 | 1 | 1 | 1 | -1 |
The two's complement operator is defined as take the one's complement and then add one. It is important to note that applying this operator twice to an n-bit number always produces the original value. So, for example, the two's complement of 0101 is 1011 and the two's complement of 1011 is 0101.
The two's complement number system havs one annoying feature, and that is, it cannot representa the negation of the most negative number. In 4 bits, for example, the value -8 is represented as 1000, but there is no 4-bit two's complement representation of +8. If you apply the two's complement operator to 1000 you get 1000!
Despite this, two's complement arithmetic is the dominant system used on all modern computers! Among the advantages of this system are that there are no problems with multiple representations of zero. Applying the two's complement operator to 0000 gives 0000 after we discard the carry out of the high bit. Another advantage is that odd numbers always have a one in their least significant bit, whether they are positive or negative. Similarly, all two's complement numbers that are evenly divisible by 4 end in 00, and all that are evenly divisible by 8 end in 000, no matter what the sign.
The fundamental reason for the popularity of two's complement numbers is that arithmetic is trivial. To add two two's complement numbers, just treat all bits as magnitude bits, even the most significant bit that you might think of as a sign bit.
To subtract two two's complement numbers, one's complment the number to be subtracted, then add the two numbers plus one. Using C notation (which is also C++ and Java notation), - is the two's complement operator and ~ is the one's complement operator, the following lines of code are all equivalent:
A - B |
A + -B |
A + (~B + 1) |
(A + ~B) + 1 |
Note that with two's complement subtraction, a carry of one into any bit position means, in essence, don't borrow from this position. This seems an odd way of handling borrows, but it works.
Warning: As was the case with one's complement arithmetic, many students get confused by the use of the term two's complement to mean both the name of the number system and the name of the operator used to negate numbers in that system! If someone says: "Take the two's complement of x," or "two's complement x" that means to apply the operator; the number of bits in the result will be the same as the number of bits in x. If someone says: "write x as a 4-bit two's complement number," that means to use the number system.
The two's complement number system turns out to be a strange place value system, in which the "sign bit" has a value that is negative. Thus, in addition to the obvious ways of converting two's complement numbers to decimal (if negative, write down a minus sign, then two's complement it to create a positive number, then convert that to decimal), we can do the conversion using the sum of the place values. For the 8 bit two's complement system, the place values are:
-128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 |
101010112 = -128+32+8+2+1 = -85
When adding two two's complement numbers, overflow detection is not as simple as looking for a carry out of some bit position. If the two numbers being added were of opposite sign, the sum must lie between them, and overflow is impossible. If the numbers being added were of the same sign, overflow is possible, and if it occurs, the sign of the result will differ from the sign of the two numbers being added. Alternately, this turns out to be equivalent to asking if the carry into the sign position is the same as the carry out of the sign position -- in adding negative numbers, there should always be a carry both into and out of the sign, and in adding positive numbers, there should never be a carry in or carry out of the sign.
As an aside, 2's complement numbers have a strong relationship to the 10's complement number system in decimal, sometimes known as the odometer number system. To compute the 10's complement of a number, subtract every digit from 9, then add 1 to the result. So, -1, as a 6-digit 10's complement number, is represented by 999999, and -2 is 999998.
There are other number systems that see occasional use. For example, there is the biased number systems, in which a bias is added to the abstract value in order to guarantee a positive value, and then that value is represented in binary. The most common bias used for n-bit numbers is 2n-1. Here is an example, in 4 bits:
0 | 0 | 0 | 0 | -8 | 1 | 0 | 0 | 0 | 0 | |||
0 | 0 | 0 | 1 | -7 | 1 | 0 | 0 | 1 | 1 | |||
0 | 0 | 1 | 0 | -6 | 1 | 0 | 1 | 0 | 2 | |||
0 | 0 | 1 | 1 | -5 | 1 | 0 | 1 | 1 | 3 | |||
0 | 1 | 0 | 0 | -4 | 1 | 1 | 0 | 0 | 4 | |||
0 | 1 | 0 | 1 | -3 | 1 | 1 | 0 | 1 | 5 | |||
0 | 1 | 1 | 0 | -2 | 1 | 1 | 1 | 0 | 6 | |||
0 | 1 | 1 | 1 | -1 | 1 | 1 | 1 | 1 | 7 |
Biased number systems seem like oddities, but they are used in such places as floating point numbers, where they are commonly used to represent the exponent field. Biased numbers have the advantage that sorting the representations into simple binary order puts the abstract values in numerical order. This is not true for any of the other systems discussed here! Like the two's complement system, there is always at least one value that cannot be negated.
Curiously, when the bias used with n-bit numbers is 2n-1, the biased representation of some value v can be computed by taking the two's complement representation of v and then inverting the most significant bit. So, for example, -8 as a 4-bit two's complement number is 1000 and as a 4-bit biased number, it is 0000.
in simple binary order, with 0000 representing the smallest value, and 1111 representing the largest. To convert from our signed-magnitude decimal system to the biased system, add the bias (8 for the 4-bit system) to the number to be converted, then convert that sum to simple binary.
Exercises:
t) Flip a coin 8 times to produce an 8-bit binary number. What abstract value does this number represent in the signed magnitude system. Check your result by converting back to binary in the signed-magnitude system.
u) Flip a coin 8 times to produce an 8-bit binary number. What abstract value does this number represent in the one's complement system. Check your result by converting back to binary in the one's complement system.
v) Flip a coin 8 times to produce an 8-bit binary number. What abstract value does this number represent in the two's complement system. Check your result by converting back to binary in the two's complement system.
w) Flip a coin 8 times to produce an 8-bit binary number. What abstract value does this number represent in the biased number system with the default bias for 8-bit numbers. system. Check your result by converting back to binary in the biased number system.