CS代考计算机代写 assembler compiler assembly mips Number Representations

Number Representations
There are 10 types of people in this world Those who understand binary and those who don’t

Agenda • Bits, Bytes, and Words
• Numberbasesandbaseconversion – Positional notation
• Binary arithmetic and data representation – Signed numbers
– Arithmetic and overflow
– Packed Decimal, ASCII, Parity…

From Lecture 1: Below Your Program • High-level language program (in C)
swap (int v[], int k) { int temp = v[k]; v[k] = v[k+1]; v[k+1] = temp;
}
• Assembly language program (for MIPS) swap: sll $2, $5, 2 add $2, $4,$2
C compiler
lw $15, lw $16, sw $16, sw $15, jr $31
• Machine (object) code (for MIPS)
0($2) 4($2) 0($2) 4($2)
assembler
000000 00000 00101 0001000010000000
000000 00100 00010 0001000000100000 …

How do people and computers represent numbers?

Why Base 10? Why Base 2?
• Decimal: Base 10, a single number from 0-9
• Binary: Base 2, a single digit is called a bit (binary digit)
• A bit is the smallest unit of information, and can represent… –1/0
– True / False
– Yes / No
– On/Off
– used in a two-state (Boolean) logic
• Can represent anything with a sequence of binary bits, but the bit patterns have no intrinsic meaning by themselves!

Nibbles to Words • Typicallystoreinformationingroups
– a byte is a group of 8 bits • e.g. 01100101
– a nibble/nybble (a small bite) is a group of 4 bits, • e.g. 0110
– a word (MIPS) is a group of 4 bytes, or 32 bits • e.g. 01100101011001010110010101100101
• Leastsignificantbitrightmost

Numbers and Positional Notation
anan-1………a1a0 . a-1a-2……..a-m
N=෌𝑛 𝑖=−𝑚
a𝑖b𝑖 or
N = anbn + an-1bn-1 +……+ a1b + a0 + a-1b-1 + ……. +a-mb-m

• 23810
• 101102
Examples

Common Bases
Name of Base
Base
Digits used
Decimal
10
0,1,2,3,4,5,6,7,8,9
Binary
2
0,1
Octal
8
0,1,2,3,4,5,6,7
Hexadecimal
16
0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F
• We often write hex numbers preceded by 0x 10112 =1110 =138 =B16 =0xB

How many bits are needed to represent a decimal number?
• What is the largest decimal number with n digits? 10n – 1
• What is the largest binary number with m digits? 2m – 1
• For base b, the largest number is bk – 1

How many bits are needed to represent a decimal number?
• How many digits necessary for numbers up to one million?

How to Convert from one Base to Another?

Base Conversion – Decimal to Another Base
• Approach1:Makeatable – Divide by bi
– The quotient is the most significant bit – Repeat with the remainder
• Approach2:
– Divide by b
– Remainder of result is least significant bit – Repeat with the quotient

Base Conversion – Decimal to Another Base • Example: What is 52310 in binary?

Base Conversion – Decimal to Another Base • Example: What is 5324110 in hexadecimal?

Base Conversion – Other Base to Decimal • BasicApproach:Directexpansionwithpositionalweights
N = anbn + an-1bn-1 +……+ a1b + a0
• AdvancedApproach:Horner’srule N = anbn + an-1bn-1 +……+ a1b + a0
= (…((anb + an-1)b + an-2)b + … +a1)b + a0

Base Conversion – Other Base to Decimal • Examples: What is 10101012 in Decimal

Base Conversion – Other Base to Decimal • Examples: What is 1AB16 in Decimal?

Base Conversion – Base A to Base B
• Conversion from base a to base b – First convert base a to decimal
– Then convert decimal to base b
• Special cases (easier by grouping) – Binary to hexadecimal and back
• Example: 110101011012
= 0110101011012 = 6AD16
– Binary to octal and back
• Example: 7608 becomes 1111100002

Questions
• What is the largest binary number with n bits?
• Howdoweaddbinarynumbers?
• Howdowesubtractbinarynumbers?
• Why do programmers always mix up Halloween and Christmas?
• Howshouldwerepresentnegativenumbers?

How to Represent Signed Numbers?

Sign-and-Magnitude • The first approach
• Use the most significant bit to represent the sign +13= 0000 1101
-13 = 1000 1101 • Problems
– Two representations for zero: 0000 0000 and 1000 0000
– Cannot add a positive number and a negative number together

• Invert each bit! +13= 0000 1101 -13 = 1111 0010
One’s Complement
• Problems:
– Still two representations for zero 0000 0000 and 1111 1111 – Answer is off by 1
– Incorrect overflow • What is 16 + (-13)?

• The gold standard
Two’s Complement
• Invert the bits and add one! +13 = 0000 1101
What is –13?
• Unique zero 0000 0000
• MSB represents the sign. – 1 if negative
– 0 if positive
• Negative numbers are defined as -N = Bn – N

Two’s Complement
• Easily implemented in hardware
• Range from -2n-1 to +2n-1 – 1
• The complement of complement of Y is Y, i.e., -(-Y) = Y.

• 16-13=?
Two’s Complement

The Hitchhiker’s Guide to the Galaxy What is the question to life, the universe, and everything?

Binary Arithmetic
Addition
Subtraction
Multiplication
0+0=0
0-0=0
0*0=0
0+1=1
0 – 1 = 1 borrow 1
0*1=0
1+0=1
1-0=1
1*0=0
1 + 1 = 0 carry 1
1-1=0
1*1=1
• Rules in base 10 are also valid in any other base
• Subtraction often done using addition and 2’s complement
• Multiplication and division are similar. We will learn in a few lectures

Arithmetic overflow
• Typically use a fixed # of bits to represent numbers!
• Arithmeticoverflowcanoccurduringtwo’scomplement addition/subtraction

Arithmetic overflow • Example: 610 + 510 using 4 bits

Arithmetic overflow
• Typically use a fixed # of bits to represent numbers!
• Arithmeticoverflowcanoccurduringtwo’scomplement addition/subtraction
– Add 2 positive numbers and get a negative result
– Add 2 negative numbers and get a positive result.
– A minus B with A<0 and B>0 and getting positive result – A minus B with A>0 and B<0 and getting negative result • Need to take extra care when implement it on the circuits Packed Decimal (Binary Coded Decimal, BCD) • Replace each digit with its 4-bit equivalent 537210 in BCD is 0101 0011 0111 0010 • Good – User friendly? Yes! – BCD is easier for humans to parse • Bad – Wastes storage space – BCD is harder to implement in hardware Parity • Usedtocheckforcorruptdatainstorageortransmission,with two kinds: even and odd – Total # of bits with 1 must be even for even parity – Total # of bits with 1 must be odd for odd parity • Examples: • Advantage of odd parity? • Detecting multiple errors? Correcting errors? Even Parity 001010100?1 000000000?0 101010101?1 Odd Parity 111010100?0 001111011?1 000000000?1 How to Represent Characters? Character Data Codes Name bits per symbol # of symbols Comments IBM-BCD 6 64 Capital letters: A-Z, 0-9, $, etc. Not to confuse with Packed Decimal. ASCII 7 128 All letters: a-z, A-Z, 0-9, $, BEL, TAB, etc. See link below. USACII 8 256 Includes parity (even). EBCDIC 8 256 On IBM mainframes (odd parity) UNICODE 16 65,536 Can represent the letters of all languages. ASCII American Standard Code for Information Interchange UNICODE The Martian An astronaut is stranded on Mars. The communication devices are broken. Only one camera is working but no sound. How can he communicate with the Earth? 48 4F 57 41 4C 49 56 45? What was the Earth trying to say? 48 4F 57 41 4C 49 56 45? Summary • Definitions: Bits, Nibbles, Bytes, Words • Representations:numberbases,conversion • Signed numbers with 2’s complement • Other data representation – Packed Decimal (BCD) – ASCII and other character data codes – Parity Review and more information • Textbook – Section 2.4, Signed and Unsigned Numbers There are 10 types of people in this world... Those who understand binary and those who don’t