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