Computer Systems - dcs.bbk.ac.uk

Computer Systems - dcs.bbk.ac.uk

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

Recently Viewed Presentations

  • Creativity, Action, and Service (CAS)

    Creativity, Action, and Service (CAS)

    Creativity, Action, and Service (CAS) International Baccalaureate Kenmore West High School Start with Self CAS at the Center CAS Defined Creativity - arts, and other experiences that involve creative thinking Action - physical exertion contributing to a healthy lifestyle, complementing...
  • Forensics and the Law Kinds of laws  US

    Forensics and the Law Kinds of laws US

    M'Naghten. Rule" - Defendant either did not understand what he or she did, or failed to distinguish right from wrong, because of a "disease of mind." The "Irresistible Impulse" Test - As a result of a mental disease, defendant was...
  • Corporate PowerPoint Template - Standard Screen

    Corporate PowerPoint Template - Standard Screen

    Submit and track the status of Applications…all in one location - EquiNet™! Easily upload life and critical illness insurance Applications and related documents; all at the click of a button on a site that ensures your clients' information is kept...
  • cs164: Introduction to Programming Languages and Compilers

    cs164: Introduction to Programming Languages and Compilers

    FORTRAN I (1954-57) Langauge, and the first compiler. Produced code almost as good as hand-written. Huge impact on computer science (laid foundations for cs164) Modern compilers preserve its outlines. FORTRAN (the language) still in use today. By 1958, >50% of...
  • The French Revolution

    The French Revolution

    The Seigneurial System. Feudal method of land ownership and organization. Peasant labor. Receiving a seigneurial grant. S. Since the Middle Ages, France and other European countries were structured on a system called feudalism. Part of this system was a method...
  • Domain: In a set of ordered pairs, (x,

    Domain: In a set of ordered pairs, (x,

    Domain: In a set of ordered pairs, (x, y), the domain is the set of all x-coordinates. Range: In a set of ordered pairs, (x, y), the range is the set of all y-coordinates. The set of ordered pairs may...
  • 552: Computer Networks

    552: Computer Networks

    Loss (e.g. TCP New Reno, SACK) Delay (e.g. TCP Vegas) Easily deployable. Robustness? Wireless? Exercise. Buffer size B at the bottleneck queue. Link capacity C. Propagation delay T. What's the congestion window for a flow at the knee? Cliff?
  • Coeliac Disease: Not a Fad

    Coeliac Disease: Not a Fad

    Legally, a gluten free food has less than 20mg of gluten per kg and has to be lab tested. Most people with coeliac disease do avoid wheat, rye and barley very well. However, many pick up gluten without knowing it...