Binary Representations Integers
The Big Picture • 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 …
Agenda • Bits, Bytes, and Words
• Numberbasesandbaseconversion – Unsigned Integers
– Signed Integers
• Binaryarithmetic
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 • A bit is the smallest unit
• Typically store information in groups – 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 is a group of 4 bytes, or 32 bits
• e.g. 01100101011001010110010101100101 • We will see it in MIPS
• Least significant bit at the right most
How to Represent Unsigned Integers?
Numbers and Positional Notation • A number with n digits in base b: an-1 … a1 a0
• Therealvalue:N=an-1 bn-1 +…+a1b1 +a0b0 • 23810
• 110102
What is the largest unsigned integer with n digits? • What is the largest decimal number with n digits?
10n – 1
• What is the largest unsigned integer in base 2 with n digits?
2n – 1
• What is the largest unsigned integer in base b with n digits? bn – 1
How many bits are needed to represent an unsigned integer?
• How many digits are needed for numbers up to one million? • Decimal:
• Binary:
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 = B16 = 0xB
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
Base Conversion – Other Base to Decimal
• Examples: What is 10101012 in Decimal
• It would be useful to remember what 2i is
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
The Hitchhiker’s Guide to the Galaxy What is the question to life, the universe, and everything?
How to Represent Signed Integers?
Signed Integers
• We will show you 3 approaches – Add a sign bit
– One’s Complement
– Two’s Complement
• Yourcomputerisusingtwo’scomplement
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)?
Two’s Complement
• The gold standard: Invert the bits and add one! • +13 = 0000 1101
• What is –13?
• Easily implemented in hardware • Uniquezero
0000 0000
• MSB represents the sign. – 1 if negative
– 0 if positive
Decimal
Binary
0
000
1
001
2
010
3
011
-4
100
-3
101
-2
110
-1
111
Two’s Complement • Negative numbers are defined as -Y = Bn – Y
• Range from -2n-1 to 2n-1 – 1
• The complement of complement of Y is Y, -(-Y) = Y.
Decimal
Binary
0
000
1
001
2
010
3
011
-4
100
-3
101
-2
110
-1
111
Binary Arithmetic
Addition
Subtraction
Multiplication
0+0=0
0-0=0
0*0=0
0+1=1
0 – 1 = 0 + (-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
• Subtractionoftendoneusingadditionand2’scomplement
• 16-13=?
Two’s Complement
Review and more information
• myCourses Notes
– binary-representation.pdf – twos-complement.pdf
There are 10 types of people in this world Those who understand binary and those who don’t