CS1100 – Introduction to Programming

Lecture 3

Instructor: Shweta Agrawal (shweta.a@[Link])

 The Computing Machine

• The computer is made up of a processor and a memory.

 The Computing Machine

• The computer is made up of a processor and a memory.

• The memory can be thought of as a series of locations to
store information.
 The Computing Machine

• A program is a sequence of instructions assembled for some

given task.
• Most instructions operate on data.
• Some instructions control the flow of the operations.
The Computing Machine : von Neuman Architecture
A brief look into the history...
From Abacus to Apple

• Counting frame.
• One of the earliest form
of calculator.
• Still used by kids to do
fast simple arithmetic.
 From Abacus to Apple

• Counting frame.
• One of the earliest form
of calculator.
• Still used by kids to do
fast simple arithmetic.

• Followed by mechanical calculators by B. Pascal (1642),

G. W. Leibniz (1671).
• Used cogs / interlocking gears.
• Performed +, −, ∗, /√.
• Leibniz is credited of creating the binary system.
Jaquard looms (1804)
Charles Babbage (1791–1871)

• Regarded as the “Father

of Computer”.
• Conceived of a machine
that has all the parts of a
modern computer, input,
a memory, a processor,
and an output (1850).
 Difference Engine (1850)

Difference engine built from Babbage’s design

(London Science Museum).
Ada Lovlace (1815–1852)

• “Wrote” the description

of the mechanical
computer of Babbage.
• Regarded as the first
programmer ever.
• The programming
language ADA is named
after her.
Alan Turing (1912 – 1954)

• Father of Theoretical
Computer Science (TCS)
and Artificial Intelligence
(AI).
• Turing machine – a
model for a general
purpose computer.
• Turing test – how
intelligent is a machine?
 First Electronic Computer : ENIAC 1946

• 50,000 vacuum
tubes, diodes,
relays, resistors,
capacitors.
• 5 million
hand-soldered
joints.
• Weighed 27 tons.
• Covered 167m2
area.
• Consumed 150
Electronic Numerical Integerator kW of power.
And Calculator.
 1946 – 1976

Integrated Circuits
Transistors
 1946 – 1976

Integrated Circuits
Transistors

Apple Macintosh
 Today’s World : Core i7 Processor

2008-15: Intel Core i7 Processor

Clock speed: > 2.5 GHz
No. of Transistors: 0.731 − 1.3B
Doubles every two years (Moore’s law!)
Technology: 45 − 22nm CMOS Area: 263 − 181mm2 .
Nowadays: Multicore (as clock speed increased) with cooling units!
Modern computing devices
Data Centers: Processing/Storing Huge volume of data
Even Cooling them is a big deal ...
The Computing Machine : von Neuman Architecture
 The Computing Machine

• A program is a sequence of instructions assembled for some

given task.
• Most instructions operate on data.
• Some instructions control the flow of the operations.
 How does the computer represent data?

• To store : Numbers, text, graphics and images, video, audio,

program instructions.
 How does the computer represent data?

• To store : Numbers, text, graphics and images, video, audio,

program instructions.
• In some way, all information is digitized - broken down into
pieces and represented as numbers.
 How does the computer represent data?

• To store : Numbers, text, graphics and images, video, audio,

program instructions.
• In some way, all information is digitized - broken down into
pieces and represented as numbers.
• Example : Representing Text Digitally.
• Every character is stored as a number, including spaces, digits,
and punctuation.
• Corresponding upper and lower case letters are separate
characters.
 The ASCII table
American Standard Code for Information Interchange (ASCII).
 The ASCII table
American Standard Code for Information Interchange (ASCII).
 But, how does number get stored?

Number Systems.
• Decimal (base 10 - uses 10 symbols {0 . . . 9}. Eg : 0, 1, 2, 3,
4, 5, 6, 7, 8, 9, 10, 11, 12, 13 . . ..
 But, how does number get stored?

Number Systems.
• Decimal (base 10 - uses 10 symbols {0 . . . 9}. Eg : 0, 1, 2, 3,
4, 5, 6, 7, 8, 9, 10, 11, 12, 13 . . ..
• Unary (base 1 - uses 1 symbol)
Eg : 1, 11, 111, 1111, . . ..
 But, how does number get stored?

Number Systems.
• Decimal (base 10 - uses 10 symbols {0 . . . 9}. Eg : 0, 1, 2, 3,
4, 5, 6, 7, 8, 9, 10, 11, 12, 13 . . ..
• Unary (base 1 - uses 1 symbol)
Eg : 1, 11, 111, 1111, . . ..
• Binary (base 2) – uses 2 symbols {0,1})
Eg : 0, 1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010 . . .
 But, how does number get stored?

Number Systems.
• Decimal (base 10 - uses 10 symbols {0 . . . 9}. Eg : 0, 1, 2, 3,
4, 5, 6, 7, 8, 9, 10, 11, 12, 13 . . ..
• Unary (base 1 - uses 1 symbol)
Eg : 1, 11, 111, 1111, . . ..
• Binary (base 2) – uses 2 symbols {0,1})
Eg : 0, 1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010 . . .
• Octal (base 8 – uses 8 symbols {0 . . . 7})
Eg : 0, 1, 2, 3, 4, 5, 6, 7, 10, 11, 12, 13 . . .
 But, how does number get stored?

Number Systems.
• Decimal (base 10 - uses 10 symbols {0 . . . 9}. Eg : 0, 1, 2, 3,
4, 5, 6, 7, 8, 9, 10, 11, 12, 13 . . ..
• Unary (base 1 - uses 1 symbol)
Eg : 1, 11, 111, 1111, . . ..
• Binary (base 2) – uses 2 symbols {0,1})
Eg : 0, 1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010 . . .
• Octal (base 8 – uses 8 symbols {0 . . . 7})
Eg : 0, 1, 2, 3, 4, 5, 6, 7, 10, 11, 12, 13 . . .
• Hexadecimal(base 16 – uses A-F for 10-15)
Eg : 0, 1, ..., 9, A, B, C, D, E, F, 10, 11, ... 19, 1A, 1B, ...
 But, how does number get stored?

Number Systems.
• Decimal (base 10 - uses 10 symbols {0 . . . 9}. Eg : 0, 1, 2, 3,
4, 5, 6, 7, 8, 9, 10, 11, 12, 13 . . ..
• Unary (base 1 - uses 1 symbol)
Eg : 1, 11, 111, 1111, . . ..
• Binary (base 2) – uses 2 symbols {0,1})
Eg : 0, 1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010 . . .
• Octal (base 8 – uses 8 symbols {0 . . . 7})
Eg : 0, 1, 2, 3, 4, 5, 6, 7, 10, 11, 12, 13 . . .
• Hexadecimal(base 16 – uses A-F for 10-15)
Eg : 0, 1, ..., 9, A, B, C, D, E, F, 10, 11, ... 19, 1A, 1B, ...
 Quick Primer on Number System : Base n

Take every ”digit” and multiply by increasing powers of n and add.

 Quick Primer on Number System : Base n

Take every ”digit” and multiply by increasing powers of n and add.

 Converting from Decimal to Binary

Conver the decimal number 39 to binary (base 2).

 Which Number System? Binary !

• Devices that store and process information are cheaper and

more reliable if they have to represent only two states.
 Which Number System? Binary !

• Devices that store and process information are cheaper and

more reliable if they have to represent only two states.
• A single bit can represent two possible states, like a light bulb
that is either on (1) or off (0). Hence representable by even
voltage levels in wires.
 Which Number System? Binary !

• Devices that store and process information are cheaper and

more reliable if they have to represent only two states.
• A single bit can represent two possible states, like a light bulb
that is either on (1) or off (0). Hence representable by even
voltage levels in wires.
• The other number systems can be ”encoded in” binary
 Which Number System? Binary !

• Devices that store and process information are cheaper and

more reliable if they have to represent only two states.
• A single bit can represent two possible states, like a light bulb
that is either on (1) or off (0). Hence representable by even
voltage levels in wires.
• The other number systems can be ”encoded in” binary
 Representing values in Binary

If we have m bits, we can represent 2m unique different values.

 Representing values in Binary

If we have m bits, we can represent 2m unique different values.

A useful circle :
 Representing negative numbers

Sign Magnitude notation

• Use one bit for sign, others for magnitude of the number.
 Representing negative numbers

Sign Magnitude notation

• Use one bit for sign, others for magnitude of the number.

Sign Magn.
0 0 0 0
0 0 1 +1
0 1 0 +2
0 1 1 +3
1 0 0 0
1 0 1 -1
1 1 0 -2
1 1 1 -3
 Representing negative numbers

Sign Magnitude notation

• Use one bit for sign, others for magnitude of the number.

Sign Magn.
0 0 0 0
0 0 1 +1
0 1 0 +2
0 1 1 +3
1 0 0 0
1 0 1 -1
1 1 0 -2
1 1 1 -3

• using n bits: −(2n−1 − 1) . . . (2n−1 − 1).

• zero has two representations.
 Representing negative numbers
Ones complement notation
• for a negative number n, represent the number by the bit
complement of its binary rep. using k bits.
 Representing negative numbers
Ones complement notation
• for a negative number n, represent the number by the bit
complement of its binary rep. using k bits.
Sign Magn. Ones comp.
0 0 0 0 0
0 0 1 +1 +1
0 1 0 +2 +2
0 1 1 +3 +3
1 0 0 0 -3
1 0 1 -1 -2
1 1 0 -2 -1
1 1 1 -3 0
 Representing negative numbers
Ones complement notation
• for a negative number n, represent the number by the bit
complement of its binary rep. using k bits.
Sign Magn. Ones comp.
0 0 0 0 0
0 0 1 +1 +1
0 1 0 +2 +2
0 1 1 +3 +3
1 0 0 0 -3
1 0 1 -1 -2
1 1 0 -2 -1
1 1 1 -3 0
• using n bits: −(2n−1 − 1) . . . (2n−1 − 1).
• zero has two representations.
• not very widely used representation.
Representing negative numbers - A neat trick
Representing negative numbers - A neat trick
Representing negative numbers - A neat trick
 Representing negative numbers - A neat trick
Twos complement notation
• for a positive number n, represent the number by its binary
rep. using k bits.
• for a negative number −n, represent the number as 2k − n.
 Representing negative numbers - A neat trick
Twos complement notation
• for a positive number n, represent the number by its binary
rep. using k bits.
• for a negative number −n, represent the number as 2k − n.
Sign Magn. Ones comp. Twos comp.
0 0 0 0 0 0
0 0 1 +1 +1 +1
0 1 0 +2 +2 +2
0 1 1 +3 +3 +3
1 0 0 0 -3 -4
1 0 1 -1 -2 -3
1 1 0 -2 -1 -2
1 1 1 -3 0 -1
 Representing negative numbers - A neat trick
Twos complement notation
• for a positive number n, represent the number by its binary
rep. using k bits.
• for a negative number −n, represent the number as 2k − n.
Sign Magn. Ones comp. Twos comp.
0 0 0 0 0 0
0 0 1 +1 +1 +1
0 1 0 +2 +2 +2
0 1 1 +3 +3 +3
1 0 0 0 -3 -4
1 0 1 -1 -2 -3
1 1 0 -2 -1 -2
1 1 1 -3 0 -1
• using n bits: −(2n−1 ) . . . (2n−1 − 1).
• widely used representation.
 Representing negative numbers

Arithmetic with these representations

Sign Magn. Ones comp. Twos comp.

0 0 0 0 0 0
0 0 1 +1 +1 +1
0 1 0 +2 +2 +2
0 1 1 +3 +3 +3
1 0 0 0 -3 -4
1 0 1 -1 -2 -3
1 1 0 -2 -1 -2
1 1 1 -3 0 -1
 Representing negative numbers

Arithmetic with these representations

Sign Magn. Ones comp. Twos comp.

0 0 0 0 0 0
0 0 1 +1 +1 +1
0 1 0 +2 +2 +2
0 1 1 +3 +3 +3
1 0 0 0 -3 -4
1 0 1 -1 -2 -3
1 1 0 -2 -1 -2
1 1 1 -3 0 -1

• 2 + (−3)
 Representing negative numbers

Arithmetic with these representations

Sign Magn. Ones comp. Twos comp.

0 0 0 0 0 0
0 0 1 +1 +1 +1
0 1 0 +2 +2 +2
0 1 1 +3 +3 +3
1 0 0 0 -3 -4
1 0 1 -1 -2 -3
1 1 0 -2 -1 -2
1 1 1 -3 0 -1

• 2 + (−3)
• 3 + (−2)
More examples : The case of 4 bits
More examples : The case of 4 bits
 More examples : The case of 4 bits

Overflow Detection Rule : If two numbers with the same sign

(both positive or both negative) are added, then overflow occurs if
and only if the binary representation of the result has the opposite
sign.
 What to do?

How to Detect it? : The technique of overflow detection is easily

implemented in electronic circuitry, and it is a standard feature in
digital adder circuits.
How to Prevent it?: Use more bits!