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