Number Systems and Computer Arithmetic
Before the Lecture
◆Online Quiz
Copyright By PowCoder代写 加微信 powcoder
– Bring your computer to the classroom for ~20 mins?
– Send me an email if you have problem (e.g., no laptop) – Perhaps you are choosing online?
– Any suggestions?
Before the Lecture
◆Feedback for the Lab sessions?
◆Last year, full online mode and it works well; but
the university requires f2f for labs
Recap of the First Lecture
◆What are the three basic components in a computer system? (the figure)
Recap of the First Lecture
◆How is a program executed in computer?
– What is an instruction cycle?
– What are the steps for executing an instruction? – Some important registers. PC?
Today’s Lecture: Two Parts
◆Part I: Number Systems – how do we represent “numbers”?
– we need a systematic representation of numeric values – it’s the foundation of science!
– understand different representations (number systems):
decimal, binary, hexadecimal
– know how to convert numbers among different representations
Today’s Lecture: Two Parts
◆Part II: Computer Arithmetic – how does a computer compute on numbers?
– number representation in computer: 2’s complement – addition and subtraction
– multiplication
– floating point notation
An Overview of Number Systems ◆Everyday example: 2441 – decimal system
◆The common feature of a number system
– a base B ( e.g., B = 10)
– B distinct symbols, where each symbol is a number (e.g., 0,1,2,3,4,5,6,7,8,9)
– a writing convention to represent a particular number as an abstract object ( e.g., 2441 )
An Overview of Number Systems
◆Example: decimal system – for a number 103
the decimal system notation (writing convention)
the expression to interpret its meaning; note: B = 10, the exponent indicates the position
Commonly Used Number Systems
– B = 2, so we have 2 symbols: 0, 1
pay attention to the common feature in the expression of the previous example 103
◆Hexadecimal
– B = 16, 16 symbols: 0,…,9, A, B, C, D, E, F
Question: based on what we have learned so far, what’s the meaning of 103?
It’s not clear! we need a subscript to denote the number system we are using!
So, What’s the General Rule?
◆Number representation: for an integer X with n digits, we write it as
◆Its decimal value is expressed as:
What about Fractional Numbers?
◆Given a real number with fraction (n: number of integers, m: number of fractions, “.” as fraction separator):
◆Its decimal value is expressed as:
Class Exercise
◆Compute the decimal value of
What we have learned so far?
(1) representations – decimal, binary, hexadecimal
(2) converting numbers in binary and hexadecimal systems to decimal system
There are some other important conversions we need to know
Converting a Decimal Integer N to Binary
◆Goal: convert a decimal integer N to its binary representation
◆Example: N = 12 → (1100)2, how can we get the binary symbols 1, 1, 0, 0 ?
◆How can you design such an algorithm to do the conversion automatically?
Converting a Decimal Integer N to Binary ◆Intuition: N can be written as
◆It means that
if we divide N by 2, we can get
remainder (we got a_0 !)
remainder (we got a_1!)
we take the quotient and divide it by 2, we can get
Converting a Decimal Integer N to Binary
◆Algorithm: repeatedly take the quotient and divided it by 2 and take the remainder as output digit
◆When to stop: until the quotient is 0
Converting a Decimal Integer N to Binary
stop when the quotient is 0
Converting a Decimal Fractional Number (<1) to Binary ◆Similar idea: Multiplication Method multiply by 2: integer (either 0 or 1; fraction Note, F < 1) take the integer as the output digit, and multiple the fraction by 2 repeat Converting a Decimal Fraction to Binary Example: F = 0.45 However, when to stop? Note: in most cases, there is not exact representation we can only convert the fraction to a binary number up-to-k precision after decimal point Class Exercise ◆Get the binary representation of F = 0.35 ◆Can you discover any pattern? ◆How about F = 0.25 Converting a Decimal Fractional Number (>1) to Binary ◆F = 123.23?
Converting Binary to Hexadecimal
◆Idea is very simple: convert every 4 binary digits to a hexadecimal number
11111001000 . 111100001
011111001000 . 111100001000
for integer part, make every 4 digits as a group from right to left
for fractional part, make every 4 digits as a group from left to right
Converting Binary to Hexadecimal
Hexadecimal notation is normally used to replace
binary notation for better readability by people; easy to convert between binary and hexadecimal
Some Thought
◆For a number with n digits in number system with base B, what is the total number of different values the n digits can represent?
◆Common number systems: decimal, binary, hexadecimal
– what define a number system: base, symbols, writing convention
◆The conversion between two number systems ◆Reading materials – slides and try a few exercises
◆Part II: Computer Arithmetic ◆Study goals:
– number representation: 2’s complement – addition/subtraction
– multiplication
– floating point notation
◆Reading materials
– chapter 9.1 – 9.2, 9.3 (no division), 9.4, concepts in 9.5 (no details needed)
Arithmetic & Logic Unit (ALU)
– the actual part of the computer that performs arithmetic and
logical operations on data
– all other parts cooperate together to send data to ALU for processing, and take results out
ALU’s Inputs and Outputs
Control Unit: give instructions on what to do Registers on the left: buffers to hold input data Flags: indicate status of instruction result Registers on the right: buffers to hold output data
An Illustrative Simple Adder
Note: we use unsigned number of n bits (binary representation)
A = 10101010, B = 00110011
But, is this unsigned number representation enough?
– what if B = 10101010?
– what if A and B are signed numbers? – we need
some mechanism to represent the sign of a number
Number Representation in Computers ◆What’s your thought?
– let’s see what we already did: -1 and +1
– we use some indicators “-” and “+” to indicate the sign
◆First try: Sign-Magnitude Representation
– use the leftmost digit (bit) to represent sign – sign bit
sign bit = 0: positive number sign bit = 1: negative number
Sign-Magnitude Representation
◆Question: for an n bit system, how many different numbers can a sign-magnitude system represent?
Sign-Magnitude Representation
◆Question: for an n bit system, how many different numbers can a sign-magnitude system represent?
– for a given sign, there are 2^{n-1} values
– two signs, we have 2 * 2^{n-1} = 2^n values
– but really? what if the magnitude part is filled with all zeros? – we have two representations for the value 0
– it can only represent 2^n – 1 numbers
Drawbacks of Sign-Magnitude Representation
◆Two representations of value 0 – hard to test for 0, which is a very frequent operation
◆Addition and subtraction need to consider both sign and magnitude – complicated because need to first check the sign and then compute
◆Complicated circuit and computationally expensive ◆Sign-Magnitude representation is rarely used in
2’s Complement Representation ◆Given n binary bits
◆Basic rules:
– (1) positive numbers and zero are represented in the same
fashion as in the sign-magnitude system
Range: from 0 000…000 to 0 111…111 (value from 0 to 2^{n-1} -1) how many numbers? 2^{n-1}
2’s Complement Representation ◆ Basic rules:
– (2) negative numbers are represented as the complement of the corresponding positive number
– complement: given a number A (n binary bits), we say B is the 2’s complement of A if A+B = 2^n (100000000) (n +1 bits!)
-example:whenn=3, 001→ 111.why?001+111=1000= 2^3
2’s Complement Representation
◆ Exercise: suppose we have 3 bits
– first write the representation of +3, +2, +1, and 0
– then write the representation of -3, -2, -1
an extra representation to represent -4
2’s Complement Representation ◆ Basic rules:
– (2) negative numbers are represented as the complement of the corresponding positive number
Range: from 1 000…000 to 1 111…111 (value from – 2^{n-1} to -1) how many numbers? 2^{n-1}
summary: for n bits, 2’s complement system can represent 2^n different values(2^{n-1}-1 positive+0+2^{n-1}negative)
example: n = 3, +3,+2,+1,0,-1,-2,-3,-4
How to Get the 2’s Complement
◆ Problem: given a binary number of n bits, how to
get it’s 2’s complement?
– example: given A = 0011 0101, what’s its 2’s complement?
◆Method 1: by definition of 2’s complement
– B is A’s 2’s complement if A + B = 2^n
– given A, B = 2^n – A
– example: 1 0000 0000 – 0011 0101 (A) = 1100 1011 (B)
How to Get the 2’s Complement
◆Method 2: flip the bits then add 1 (Important!)
– given A = 0011 0101
– flip the bits of A: 1100 1010
– add1:11001010+1=11001011=B
– verify: A + B = 0011 0101 + 1100 1011 = 1 0000 0000
How to Write a Decimal in 2’s Complement Form
◆Range: a 2’s complement of n bits can represent decimal values from – 2^{n-1} to 2^{n-1} -1
◆Given a decimal integer D:
– if D > 0: the leftmost bit is 0, and the rest (n-1) bits represent
its magnitude (sign-magnitude)
– if D < 0: use sign-magnitude to represent -D, then get its 2’s complement
Class Exercise
◆Represent -18 (decimal) in the 8 bit – 2’s complement form
Class Exercise
◆Represent -18 (decimal) in the 8 bit – 2’s complement form
- 18 = 0001 0010
- method 2: 1110 1101 → 1110 1110
2’s Complement Form to Decimal
◆Given 2's complement form, how to get D
- Observation: first bit 0 -> positive, 1 -> negative
– If starts with 0, easy to get D (same as sign-magnitude)
– If starts with 1, get it’s 2’s complement (which starts with 0), then get D, and take -D
What we have learned so far?
(1) computers use 2’s complement system to represent integers
(2) next: how to do arithmetic operations with 2’s complement representation (addition, subtraction, multiplication)
Addition in 2’s Complement
◆Feature: the addition of two numbers in 2’s
complement system does not need any sign detection
– example (4 digit): A = 1101 (-3), B = 0010 (2)
– A+B=1101+0010=1111=?
– 1111’s 2’s complement is 0001 (which is 1), so we know 1111 is -1
Overflow Detection in 2’s Complement
◆How about -1 + (-2)? what’s the problem?
– -1=1111,-2=1110
– -1+(-2)=1111+1110=11101=-3
– 1 is the carry forward bit – the result –3 seems right if we ignore it
◆How about -5 + (-4)? what’s the problem?
– -5=1011,-4=1100
– -5+(-4)=1011+1100=10111=7
– The result 7 is not right if we ignore it
Overflow Detection in 2’s Complement
◆How about -1 + (-2)? what’s the problem?
– -1=1111,-2=1110
– -1+(-2)=1111+1110=11101=-3
– Negative + negative = negative (possible)
◆How about -5 + (-4)? what’s the problem?
– -5=1011,-4=1100
– -5+(-4)=1011+1100=10111=7
– Negative + negative = positive (no possible)
Overflow Detection
◆ALU’s overflow detection rule in 2’s complement: if two numbers are added, and they are both positive or both negative , then overflow occurs if and only if the result has the opposite sign (no possible!)
Subtraction in 2’s Complement
◆Operation A – B can be computed by A + (-B), where (- B) is the 2’s complement of B
– 0011 1100 – 0010 1101 = 0011 1100 + (- 0010 1101) – = 0011 1100 + 1101 0011
Representation of Different Number of Bits ◆Positive number: 18 in decimal
– 8 bit representation: 0001 0010
– 16 bit representation: 0000 0000 0001 0010 – packing with leading 0’s on the left
◆Negative number: -18 in decimal
– 8 bit representation: 1110 1110
– 16 bit representation: 1111 1111 1110 1110 – packing with leading 1’s on the left
Multiplication
◆Focus on unsigned binary numbers ◆Dealing with negative numbers
Paper and Pencil Example of Unsigned Binary Numbers
multiplicand: 1011 multiplier: 1101
we get one partial product for each bit in the multiplier
then, we add all the partial products together
partial product is the copy of the multiplicand if bit = 1, and all zeros if bit = 0
Paper and Pencil Example of Unsigned Binary Numbers A closer look: multiplication is the
addition of “shifted” multiplicand The bits in Multiplier controls the
operation:
Bit = 1: shift and add Bit = 0: shift
How Can a Computer Do It Automatically? ◆Perform running addition on the partial products
– do not need to wait for all the partial products
– add the accumulated result with the current partial product
◆Use two operations “add” and “shift” to implement the addition
– if bit in the multiplier is 0: just shift
– if bit in the multiplier is 1: add and shift
How Can a Computer Do It Automatically?
This is a circuit for multiplication: A, B, Q are registers to store accumulated result, Multiplicand, and Multiplier, respectively
How Can a Computer Do It Automatically? Initialization
The bits in Q decide the operation
Example: 1001 X 1100
An Optimized Version of Circuit (FYI)
An improved circuit for multiplication
Two improvements
(1) Previously, we shift Multiplicand (B) to the left, now we can shift the accumulated result (A) to the right (same for adding two bit-strings)
(2) We can reuse the space of Q
Note: comparing to the previous circuit, both B and A now have n bits
How Can a Computer Do It Automatically?
A comparison of the logics of two circuits: the difference lies in the shift operation
Multiplication with Negative Multipliers
◆The previous algorithm on unsigned binary numbers
does not work directly on 2’s complement representation
◆Straight forward solution
– ignore the sign, compute the multiplication, and then take the 2’s
complement of the result
– an alternative: fast multiplication on 2’s complement representation – the Booth’s algorithm (Chap. 9.3, not required)
What we have learned so far?
(1) simple arithmetic on integers in computer
(2) next: how to deal with fractional numbers in computer?
Fraction Number Representation
◆First try: integer part + radix point (.) + fractional part
– example: 1001.1010
◆The issue: where should we put the radix point? – if we use n = 8 bits, choices of I + F: 7+1, 6+2, …, 2+6, 1+7
– if the radix point is in a fixed location, the range of data is very limited (not flexible)
– note: the total number of different numbers that could be represented is the same; the range of numbers are different
Can We Do Better?
◆Consider decimals:
– 976,000,000,000,000 → 9.76 x 10^{14}
– 0.0000000000000976 → 9.76 x 10^{-14}
– what we have done: dynamically slide the decimal point to a convenient location and use the exponent of 10 to keep track of the location
– use this similar idea to represent binary fractional numbers in computers
Floating Point (FT) Representation ◆Represent a number in the form:
the number can be stored in a binary word with three fields: Sign: plus or minus
Significand S
Exponent E
(the base B is often implicit)
Floating Point (FT) Representation
◆The Significand S and The Radix Point
– there are different ways to represent the same number
Two conventions:
(1) the radix point is on the right of the left-most bit (there is only one bit on the left of the radix point) (2) the left-most digit of the significand is non-zero (for base 2, it is always 1) — normalization
As a result, a normalized nonzero number always has the following form:
Floating Point (FT) Representation ◆The Significand S and The Radix Point
Two conventions:
(1) the radix point is on the right of the left-most bit (there is only one bit on the left of the radix point) (2) the left-most digit of the significand is non-zero (for base 2, it is always 1) — normalization
As a result, a normalized nonzero number always has the following form:
b is either 0 or 1
As a result, we do not need to store the “1” in the significand, we just store bbbbbbbbbb
Floating Point (FT) Representation ◆The biased exponent E
the actual value of E = biased exponent – a fixed bias
fixed bias: 2^{k-1} -1, k is the number of bits of the “Biased exponent” field, k =8 in our case
example:k=8,bias =2^7-1=127;
if E = 20, the biased exponent = E + bias = 147 = 1001 0011
since the biased exponent is from 0 to 255, E is in the range of -127 to 128
Floating Point (FT) Representation ◆Put it together
binary number bit pattern in computer
decimal value
first row: E = 20 → biased exponent = 127+20 = 147; Significand just stores the portion after radix point forth row: E = -20 → biased exponent = 127 – 20 = 107;
Conversion: FP Bit Pattern and Binary number
◆Given a binary number, find its FP Bit Pattern
– binary: – 0.001010
– step 1 normalization: -1.01 x 2^{-3}
– step 2 get biased exponent:
– E = -3 → biased exponent = -3+127 = 124 = 0111 1100
– step 3 get significand (23 bits) : 01 0 0000 0000 0000 0000 0000
result: 1 0111 1100 010 0000 0000 0000 0000 0000
Conversion: FP Bit Pattern and Binary number
◆Given FP Bit Pattern, get the binary value, and then the decimal value
– class exercise: 00110101110100100000000000000000
The Range of 32-bit Binary Floating Point Number
Compared to 2’s complement for integer representation, they both represent 2^{32} different values, but the ranges are different
◆Computer Arithmetic
– number representation in computer: 2’s complement – addition and subtraction in 2’s complement
– multiplication (unsigned)
– floating point notation
Reading Assignment
◆For computer arithmetic
– chapter 9.1, 9,2
– chapter 9.3 (Booth’s algorithm and division are not required) – chapter 9.4
– chapter 9.5 (just concept, not required)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com