Introduction to Computer Systems Department of Computer Science and Information Systems Lecturer: Steve Maybank [email protected] Spring 2020 Week 2b: Storing Integers 21 January 2020 Birkbeck College, U. London 1 Representations of Negative Integers Put a minus sign in front of the representation for a positive integer.
Excess notation. Twos Complement notation the most popular representation for integers in computers. Brookshear, Section 1.6 2 Excess Notation Problem: represent a set of positive and negative integers using bit strings with a fixed length n
Represent 0 by 100 (n bits) Represent positive numbers by counting up from 100 in standard binary notation Represent negative integers by counting down from 100 in standard binary notation. Brookshear, Section 1.6 3 Three Bit Excess Notation n=
3 111 110 101 3 2 1 100 0 011 010 001 000 -1 -2
-3 -4 Brookshear, Section 1.6 4 Alternative Name: Excess Four Notation bit string = Binary(number+4) e.g. 110 = Binary(2+4) 011 = Binary(-1+4) Brookshear, Section 1.6 111 110 101
3 2 1 100 0 011 010 001 000 -1 -2 -3 -4 5 Examples
Find the 6 bit excess notation for the decimal numbers 7 and -6. Which decimal number has the 5 bit excess notation 10101? Birkbeck College, U. London 6 Twos Complement Notation bit twos complement notation for integers in
the range Eg. Birkbeck College, U. London 7 More Examples Four bit two' s complement representation for 5 2 4 5 16 5 11 Decimal11 Binary1011 Answer :1011 Four bit two' s complement representation for 6 2 4 6 16 6 22 Decimal 22 Binary10110 Answer : 0110 Birkbeck College, U. London
8 Example of Twos Complement Notation 0111 0110 0101 0100 0011 0010 0001 0000 7 6 5 4 3 2 1 0
1111 1110 1101 1100 1011 1010 1001 1000 -1 -2 -3 -4 -5 -6 -7 -8 n=4 The left most bit indicates the sign.
Brookshear, Section 1.6 9 Addition and Subtraction In the twos complement system subtraction reduces to addition. E.g. to evaluate 6-5 in 4 bit twos complement notation, add the tc bit strings for 6 and 5, then take the four rightmost bits. 0110 1011 === 10001 6 -5 == 1
Brookshear, Section 1.6 10 Explanation TC(6) = rightmost four bits of Binary(24+6) TC(-5) = rightmost four bits of Binary(24-5) Binary((24+6)+(24-5))= Binary(24+24 +1). The right most four bits of Binary(24+24 +1) form the bit string for TC(1). Brookshear, Section 1.6 11 Why Use Twos Complement Addition and subtraction require one circuit for addition and one circuit for negation.
This is more efficient than having a circuit for addition and a circuit for subtraction. Brookshear, Section 1.6 12 Notation Let s, t be bit strings. The concatenation of s and t is s||t, e.g. 110||001 = 110001 Let s be a bit string. Then complement(s) is the bit string obtained by reversing the bits of s, e.g. complement(110) = 001 Birkbeck College, U. London
13 Twos Complement Notation for m and -m Let TC(m) = s || 1 || t, where t is a string of zeros TC(-m) = complement[s]||1||t. Examples: n = 4, TC(3) = 0011, TC(-3) = 1101 TC(-1) = 1111, TC(1) = 0001 Brookshear, Section 1.6
14 TC(m) and TC(-m) TC(m) = rightmost bits of TC(-m) = rightmost bits of TC(m)+TC(-m) = rightmost bits of Therefore TC(m)+TC(-m) = 0 =TC(0) = TC(m-m) Brookshear, Section 1.6 15
Expression for TC(-m) Let TC(m) = s || 1 || t, where t is a string of zeros. To prove TC(-m) = complement(s)||1||t, show that s||1||t + complement(s)||1||t = 0 t+t = t = string of zeros 1+1 = 0+carry s+complement(s) = string of ones carry+string of ones = 100 Brookshear,
Section The rightmost n bits are all1.6 zero. 16 Alternative Expression TC(-m) = complement(TC(m))+1 Proof: let r be a string of 1s with the same length as t. Then complement(s||1||t)+1=(complement(s)||0||r)+1 = complement(s)||1||t Birkbeck College, U. London
17 Twos Complement and Subtraction (correct for the rightmost n bits only) Subtraction can be carried out using addition and the twos complement notation TC. This reduces the complexity of the circuits required for arithmetic Birkbeck College, U. London 18 Example Find the 5 bit twos complement
representations for the decimal integers 5 and -5. Birkbeck College, U. London 19