0 Notes1 Integers
0 Notes1 Integers
0 Notes1 Integers
Department of Computing
ComputerSystems113 Architecture110
SELFSTUDYNOTES Version1
Dr. N. Dulay
October 2007
N. Dulay
Self-Study
Welcome to the Computer Systems / Architecture course. Before the lectures start in November students are required to study some topics on their own. The topics are straightforward and shouldnt require too much effort. If youre stuck however, then you can contact me by email (nd@doc.ic.ac.uk). There are some simple exercises at the end of the notes for you to try. The website for the course is: https://www.doc.ic.ac.uk/~nd/architecture Note: the URL starts https. If you want more in-depth information on the topics then an excellent resource is Wikipedia at http://en.wikipedia.org/ The topics cover: Unsigned Integer Representation You should be able to perform radix conversion between decimal, binary and hexadecimal (base 16). You should be able to perform the four basic arithmetic operations on positive numbers in binary. Signed Integer Representation You should be able to represent signed decimal integers in twos complement, sign-and-magnitude, excess/bias and BCD. You should be able to add and subtract twos complement numbers and recognise overflows. Character Representation You should understand how computers represent characters and know of the ASCII and Unicode character sets.
N. Dulay
UnsignedIntegers
Computers process binary patterns, i.e. of patterns of 0s and 1s. To represent data within a computer we need to code it as a binary pattern.
1
The representation of integers and characters are the most important to consider because more complicated data representations can be built from them, e.g. complex numbers, dates, times, addresses, sound, video, typefaces.
2
Computer architects have employed many different schemes for representing numerical values, and there are advantages and disadvantages to each representation. Before considering these, we need to remind ourselves about binary numbers.
Binary numbers
As you know, unsigned integer numbers can be represented in bases (radices) other than base ten (decimal), for example the decimal number 14 can be represented as 16 in base 8 (octal) as 24 in base 5, as 112 in base 3 (ternary), and as 1110 in base 2 (binary). These follow from the standard technique of coding each position of the number as a power of the base: d n d n1... d 0 . For a decimal number we have:
k =0
d k *10
k =0
d k *2k
The second sum (for a binary number) also gives us a simple method to convert integers from base 2 to base 10. Example: for the decimal number 252 we have: 252 Decimal (Base 10) MS 2 100 10 2 5 10 10 1 LS 2 1 10 0 MS 1 128 2 7 1 64 2 6 1 32 2 5 1 16 2 4 1 8 2 3 1 4 2 2 0 2 2 1 11111100 Binary (Base 2) LS 0 1 2 0
3
Here MS stands for Most Significant and signifies the leftmost digit or bit. LS stands for Least Significant and signifies the rightmost digit or bit. We can make the base of a number explicit by suffixing it to the number as a subscript: 14 = 16 = 24 = 112 = 1110
10 8 5 3 2
In some computer languages we suffix the letter B (or b) to binary values e.g. 101B
1 2 3
Well also look at how computer programs are represented later in the course. Well also look at the approximation of real numbers using floating-point numbers later in the course. Spaces or underscores in binary numbers are added for readability. Spaces/underscores between groups of 4 bits (grouping right-to-left) is common.
N. Dulay
Answer: 110 0010 reading the remainder column from bottom to the top MS-bit to LS-bit 2
N. Dulay
N. Dulay
Starting from the rightmost (least significant) end, each group of 3 bits represents 1 octal digit (called an octet). 000 (0), 001 (1), 010 (2), 011 (3), 100 (4), 101 (5), 110 (6), 111 (7) Example: What is 10101 in octal? 2 10 2 Answer: 25 8 8 in binary? 101 5
3 011 Answer:
5 101
7 111
11101111
Although octal is less used these days, you should be familiar with the term.
N. Dulay
Example:
Note: We will sometimes use the suffix the letter H (or h) after a hexadecimal value instead of the subscript 16, e.g. 2A3H. Another alternative that is used in some programming languages is to prefix the hexadecimal value with 0x, e.g. 0x2A3
N. Dulay
Radix Arithmetic
Performing addition, subtraction, multiplication and division in bases other that 10 is identical to decimal arithmetic except that we use the particular base as the point of reference instead of 10. Some examples should make this clear.
Addition A + B R R Working from Right to Left While digits remain to be added Add current digits of A and B If SUM is less than R then record SUM Otherwise record difference SUM - R add (carry) 1 to next column End while Subtraction A - B when A>B R R Working from Right to Left While digits remain to be subtracted If digitof (A) >= digitof (B) then record A - B Otherwise record (R + A) B subtract 1 from digits to As left (or add 1 to digits to Bs left) End while
4 + 1 5 3
3 4 0
2 3 5
7 7
================== 7
4 5 6
3 7 3
2 6 4
8 8
================== 8
N. Dulay
Stepk 1 2 3 4 5 6 7
A +B +Carry =Carry Sum k k k k+1 k 1+0=1 1+1=10 0+0+1=1 1+1=10 1+1+1=11 1=1 =>sum1 =>carry1sum0 =>sum1 =>carry1sum0 =>carry1sum1 =>sum1
1+0+1=10 =>carry1sum0
N. Dulay
Stepk 1 2 3 4
A B =Diff k k k 10=1 00=0 11=0 01 Borrowbysubtracting1fromA A =100andA =10. 7..5 4 NowuseAinsteadofA,e.g.A B 4 4 101=1 7..5 =101togive
01
Subtract1fromA
101=1 6 7 10=1
00=0
If youre used to borrowing by adding back to B (the subtrahend), then that method will work also and you are welcome to use it. Warning: many students have forgotten how to subtract numbers and become reliant on calculators. Make sure you can subtract without a calculator!
N. Dulay
Answer Carry
1 1
1 10
The main difficulty with human division is in estimating how many times the divisor goes into the partial dividend. Most people do this mentally. Luckily for binary numbers, this is easier since we only have two choices. We will postpone the consideration of fractional results until later in the course. Example: Perform the binary division 10 0011 1111 / 1 1001 i.e. decimal 575/25 Quotient> 11001 1 0 1 0 1 1 0 0 0 1 1 1 0 1 1 0 1 1 1 1 0 0 0 1 1 1 Remainder> 1 0 1 0 1 1 1 1 0 0 0 0 1 1 0 0 1 1 0 0 1 1 1 1 1 1 1
Although the numbers in the example above are binary, you may find it useful to pretend they are decimal when performing comparisons, i.e. will 11,001 go into 10,001 (no), will it go into 100,011 (yes). If youre Greek, then the division technique taught in Greek schools works fine (try it!).
N. Dulay
SignedIntegers
Up until now we have been assuming that integers are unsigned. In addition to representing the magnitude of numbers, computer architects also need to consider the representation of the sign of a number (+ or -) and for real numbers the representation of fractional values and the representation of exponents. In this section well consider the representation of signed integers.
Bit Groups
Numbers within a computer system are not normally allowed to be of arbitrary length (size). Instead numbers are represented and manipulated in finite bit groups. The most common bit groups are the bit (1-bit), the byte (8-bit), and the word. Word size is architecture dependent but popular examples are 16-bit words, 32-bit words, and 64-bit words . Architectures often employ their own unique names for the differing sizes, for example, on the Pentium 16-bit groups are called words, 32-bit groups are called doublewords and 64-bit groups are called quadwords.
5
Bit 3 Nibble
6
14
13
12
11
10
The numbers above the bits indicate the bit position, with the least significant bit at position 0 (the rightmost end).
5 6
We shall see later in the course that there is a strong relationship between word size, the width of memory locations and the size of CPU registers. Nibble = Half-a-byte obviously :-)
N. Dulay
Bitgroup
Bits
Hex digits 1
Bit
Nibble
0to15
Byte
0to255
Word(16bit)
16
=65,536
0to65,535
Word(32bit)
32
2
8
32
=4,294,967,296
0to4,294,967,295
Nbits
N/4
N 0to2 1
Example: Show the bit pattern for the number thirteen using groups of 3,4, 5 and 6 bits. 3 bits 4 bits 5 bits 6 bits (we cant do this, since we do not have sufficient bits) 1101 01101 001101
In computing we use the following definitions for kilo (K), mega (M), giga (G) and tera (T): 10 Kilo K=2 =1024 20 2 Mega M=2 =1024 which is just over 1 million 30 3 Giga G=2 =1024 which is just over 1 billion 40 4 Tera T=2 =1024 which is just over 1 trillion
7
Any of the representations for signed integers can also be used although the range will be smaller. We will see later in the course that unsigned integers are used to address main memory locations. 8 is the ceiling operator.
N. Dulay
A common convention is to use B to signify Bytes and b for bits. For example, 4 MB means 4 Megabytes, while 4 Mb means 4 Megabits.
N. Dulay
In addition, and perhaps most important we would like to have a fast and economical hardware implementation of integer arithmetic. We will use as an example the 4-bit group, i.e. the following bit-patterns: BitPattern 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 Unsigned +0 +1 +2 +3 +4 +5 +6 +7 +8 +9 +10 +11 +12 +13 +14 +15
Hardware implementation -> minimal number of transistors AND fast arithmetic if possible.
N. Dulay
Perhaps the first thing we notice about sign & magnitude is that we have two bit patterns for zero (labelled +0 and 0). This wastes a value and requires that the hardware treat both bit patterns as zero. Sign & magnitude is the simplest representation for humans to understand, and a little bit-more costly (in transistors) than other methods to implement. Why? Because signs need to be taken into account explicitly leading to the need to implement subtractors as well as adders, for example, for addition we need to compare signs and absolute values of the numbers and then add or subtract accordingly. Comparing two absolute values is also a costly operation. Twos complement representation doesnt have these disadvantages. For an n-bit group, the sign & magnitude numbers will range from (2
n1
1) to +(2
n1
1)
N. Dulay
+0 +1 +2 +3 +4 +5 +6 +7 0 1 2 3 4 5 6 7
+0 +1 +2 +3 +4 +5 +6 +7 7 6 5 4 3 2 1 0
Like sign & magnitude, ones complement yields two representations for zero, and a 1 for the leftmost bit indicates a negative value. Ones complement is less intuitive (for humans) than sign & magnitude, but less costly to implement in hardware. Because of the two representations for zero, with ones complement the result after an operation is not always correct e.g. we must add 1 to the result of an addition if the carry out from the most significant bit is 1. It is desirable to avoid such complications in hardware. Like sign & magnitude, for an n-bit group the one's complement numbers will range from (2
n1
1) to +(2
n1
1)
Ones complement was used on some old computers and is no longer used.
N. Dulay
+0 +1 +2 +3 +4 +5 +6 +7 0 1 2 3 4 5 6 7
+0 +1 +2 +3 +4 +5 +6 +7 7 6 5 4 3 2 1 0
+0 +1 +2 +3 +4 +5 +6 +7 8 7 6 5 4 3 2 1
The first thing that strikes us with twos complement is that we only have 1 bit pattern for zero. The second thing that strikes us, is that the representation is asymmetric i.e. there is one extra negative value. Luckily the asymmetric range is a minor disadvantage compared to the nice properties that twos complement provides.
10
Perhaps the most useful property of twos complement is that subtraction can be performed by forming the 2's complement of the subtrahend and using addition instead. i.e. X Y = X + (Y) Forming the 2s complement turns out be a simple operation to implement so there is no need for a separate subtractor (as in sign & magnitude) or carry-out adjustments (as in ones complement). Twos complement is also a true complement in the sense that +X+(X) = 0 and (X) = X. For n-bits, two's complement numbers range from 2
10
n1
to +(2
n1
1)
N. Dulay
1111 1110
0001 0010
Example: Calculate 5 + (4) and 5 (2) using the twos complement clock. Conceptually we perform the addition by counting clockwise, i.e. +5 + 4 is 0101 + 1100, i.e. move 1100 (twelve) places clockwise from 0101 which arrives at 0001 = +1. Similarly for the subtraction we count anticlockwise, e.g. +5 (2) is 0101 1110 e.g. move 1110 (fourteen) places anticlockwise from 0101 which arrives at 0111=+7.
N. Dulay
Tens Complement
It is interesting to know that we can also have complements in other bases, e.g. tens complement. n The 10s complement of an n-digit decimal number X is defined as (10 X), e.g. for the 4-digit decimal number 1234 the 10s complement is 8766. Recall that the 2s complement for an n-bit n binary number X is defined as (2 X).
Example: Convert the 4-bit two's complement value 1011 to decimal. = (1 * 8) + (0 * 4) + (1 * 2) + (1 * 1) = 8 + 2 + 1 = 5 Alternatively for negative values we can negate the number (make it positive), convert to decimal & negate it. For example for 1101 we can Negate 1101 by inverting each bit and adding one giving 0101 Convert 0101 to decimal i.e. 1*4 + 1*1 = 5 Negate 5 to give 5
N. Dulay
BitPattern 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
Excess8 8 7 6 5 4 3 2 1 0 +1 +2 +3 +4 +5 +6 +7
+0 +1 +2 +3 +4 +5 +6 +7 0 1 2 3 4 5 6 7
+0 +1 +2 +3 +4 +5 +6 +7 7 6 5 4 3 2 1 0
+0 +1 +2 +3 +4 +5 +6 +7 8 7 6 5 4 3 2 1
Like two's complement, excess-n is asymmetric. Excess-n is used where it is important to be able to compare (and sort) values easily. We will return to it when we consider the representation of exponents for real numbers later in the course. Some calculators also employ excess-n numbers. Note: if n is chosen to be equal to 2 where m is the number of bits in the representation then Excess-n representation is the same as two's complement but with the sign-bit inverted.
m1
N. Dulay
Excess8 8 7 6 5 4 3 2 1 0 +1 +2 +3 +4 +5 +6 +7
+0 +1 +2 +3 +4 +5 +6 +7 0 1 2 3 4 5 6 7
+0 +1 +2 +3 +4 +5 +6 +7 7 6 5 4 3 2 1 0
+0 +1 +2 +3 +4 +5 +6 +7 8 7 6 5 4 3 2 1
BCD is obviously very easy for humans to comprehend, although a smaller range of numbers is representable compared with other binary representations, e.g. 16 bits can only represent the natural numbers 0 to 9999. Signs are handled by using two of the unused bit patterns, for example, on the VAX Architecture, the bit pattern 1100 is used for the + sign and 1101 for the sign. Confusingly however, in the VAX architecture the sign nibble occurs at the least significant end. Example. What is 837 and 837 in VAX BCD? 10 10 Unsigned value 837 is 1000 0011 0111 in BCD. 10 +837 = 1000 0011 0111 1100 in VAX BCD (+ at end) 837 = 1000 0011 0111 1101 in VAX BCD ( at end)
N. Dulay
Overflow Rule: If 2 twos complement numbers are added, and they are both positive or both negative, then overflow occurs if and only the result has the opposite sign, i.e. (+A) + (+B) = C or (A) + (B) = +C Example: Calculate 7+(6) using a 4-bit two's complement representation. (7) +(6) (+3) 1001 1010 10011 Overflow
11
N. Dulay
Overflow Rule: If 2 twos complement numbers are subtracted, and their signs are different, then overflow occurs if and only if the result has the same sign as the subtrahend. (+A) (B) = C or (A) (+B) = +C Example: Calculate 7(6) using a 4-bit two's complement representation. (+7) (6) (3) 0111 0110(Negated) 1101Overflow
N. Dulay
Characters
Computers map characters to bit patterns (unsigned integers effectively). The most common mappings in use are ASCII (pronounced as-key) and Unicode. An older mapping is IBMs EBCDIC.
12
ASCII uses 7-bits (128 bit patterns) although most computers extend this to 8 bits yielding an extra
128 bit-patterns. ASCII has 26 lowercase letters, 26 uppercase letters, 10 digits, and 32 punctuation marks. The remaining 34 bit patterns represent whitespace characters e.g. space (SP), tab (HT), return (CR), linefeed (LF) and special control characters that are used in interfacing to I/O devices. Note that the uppercase letters A-Z, lowercase letters a-z and the digits 0-9 have contiguous values. Strings are represented as sequences of characters. E.g. The name Fred is encoded as follows: English ASCII(Binary) ASCII(Hex) The 7-bit ASCII Character Set Bitpositions654 000 NUL SOH STX ETX EOT ENQ ACK BEL BS HT LF VT FF CR SO SI 001 DLE DC1 DC2 DC3 DC4 NAK SYN ETB CAN EM SUB ESC FS GS RS US 010 SP ! # $ % & ( ) * + , . / 011 0 1 2 3 4 5 6 7 8 9 : ; < = > ? 100 @ A B C D E F G H I J K L M N O 101 P Q R S T U V W X Y Z [ \ ] ^ _ 110 a b c d e f g h i j k l m n o 111 p q r s t u v w x y z { | } ~ DEL Bit positions 3210 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 F 01000110 46 r 01110010 72 e 01100101 65 d 01100100 64
12
N. Dulay
Unicodeisanewer,morecomplex,standardthatisattemptingtoprovideanumberfor
everycharacternomatterwhatthelanguage.About100,000charactershavealreadybeen defined.Thefirst65,536(16bit)characterscoverthemajoralphabetsoftheworld. Itisbecomingcommonforprogramminglanguagestosupport16bitUnicodecharacters, e.g.Java,Python.Note:thefirst127charactersofUnicodecorrespondtoASCIIcharacters. YoucanfinddefinitionsoftheUnicodecharactersathttp://www.unicode.org/charts/ Examples: UppercaseAinBasicLatin(i.e.ASCII)is0041Hex. Seepage2ofhttp://www.unicode.org/charts/PDF/U0000.pdf 3/4inLatin1is00BEHex Seepage2ofhttp://www.unicode.org/charts/PDF/U0080.pdf PiinGreekandCopticis03A0Hex. Seepage2ofhttp://www.unicode.org/charts/PDF/U0370.pdf ThedoubleconcentriccirclecharacterinThaiis0E4FHex. Seepage2ofhttp://www.unicode.org/charts/PDF/U0E00.pdf TriplerightarrowsinArrowsis21F6Hex. Seepage2ofhttp://www.unicode.org/charts/PDF/U2190.pdf
N. Dulay