Welcome Survey Due Today

• Discussion section format
• On the fence about regular vs. mega discussion? Choose regular so you can get assigned a discussion time that works for you.
• Fill out form by Friday (today 1/24) 11:59pm to get assigned a regular time (if applicable). All other students default to mega.
• Can switch section times/formats until Add/Drop deadline (W 2/12)
• 61C Scholars Pilot Program
• Scholars-specific regular discussion
• Other academic activities/socials
• Self-identify on Welcome Survey
• OK to edit/resubmit the form before deadline

Access via

• Lab00 Exercise 6 (Lab 00 due Mon 1/27) https://cs61c.org/sp25/labs/lab00/
• Ed: See Ed

Yan, SP25

02-Number Representation (1)

​

Number Representation

Great book ⇒� The Universal History of Numbers� by Georges Ifrah

​

Lecture PDF: link

CS61C

Great Ideas

in

Computer Architecture

(a.k.a. Machine Structures)

cs61c.org

Assistant

Teaching Professor

Lisa Yan

Yan, SP25

02-Number Representation (2)

​

Digital data not necessarily born Analog…

hof.povray.org

Yan, SP25

02-Number Representation (3)

​

Data input: Analog → Digital

Real world is analog!

To import analog information, we must do two things

• Sample
• E.g., for a CD, every 44,100ths of a second, we ask a music signal how loud it is.
• Quantize
• For every one of these samples, we figure out where, on a 16-bit (65,536 tic-mark) “yardstick”, it lies.

Yan, SP25

02-Number Representation (4)

​

Every Base is Base 10…?

How many rocks?

Yan, SP25

02-Number Representation (5)

​

Binary, Decimal, Hex

Agenda

• Binary, Decimal, Hex
• Integer Representations
• Sign-Magnitude,�Ones’ Complement
• Two’s Complement
• Bias Encoding

Yan, SP25

02-Number Representation (6)

​

Number vs Numeral

Numeral

A symbol or name that stands for a number

e.g., 4 , four , quatro , IV , IIII , …

…and Digits are symbols that make numerals

​

Above the abstraction line

​

​

Below the abstraction line

​

Number

The “idea” in our minds…there is only ONE of these

e.g., the concept of “4”

​

​

​

​

​

Abstraction Line

Yan, SP25

02-Number Representation (7)

​

Decimal: Base 10 (Ten) #s

Digits: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

​

Example:

3271 = 3271₁₀ = (3x10³) + (2x10²) + (7x10¹) + (1x10⁰)

Yan, SP25

02-Number Representation (8)

​

Base 2 (Two) #s, Binary

Digits: 0, 1 (binary digits -> bits)�

Example: Binary number “1101”

​

Convert to decimal:

0b1101 = 1101₂ = (1x2³) + (1x2²) + (0x2¹) + (1x2⁰)

= 8 + 4 + 0 + 1

= 13

Common binary shorthand: 0b1101

Yan, SP25

02-Number Representation (9)

​

Base 16 (Sixteen) #s, Hexadecimal

Digits: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F

10, 11, 12, 13, 14, 15

Example: Hexadecimal number “A5”

​

Convert to decimal:

0xA5 = A5₁₆ = (10x16¹) + (5x16⁰)

= 160 + 5

= 165

“Hex” for short. Common hex shorthand: 0xA5

Yan, SP25

02-Number Representation (10)

​

Convert from Decimal to Binary

E.g., 13 to binary?

Start with the columns

Left to right, is (column) ≤ number n?

• If yes, put how many of that column fit in n, subtract col * that many from n, keep going.
• If not, put 0 and keep going. (and Stop at 0)

​

13

5

1

1

1

0

1

0

0b1101

Yan, SP25

02-Number Representation (11)

​

Convert from Decimal to Hexadecimal

E.g., 165 to hexadecimal?

Start with the columns

Left to right, is (column) ≤ number n?

• If yes, put how many of that column fit in n, subtract col * that many from n, keep going.
• If not, put 0 and keep going. (and Stop at 0)

0x00A5

165

Yan, SP25

02-Number Representation (12)

​

Nibbles and Bytes

• 4 Bits
• 1 “Nibble”
• 1 Hex Digit = 16 things
• 8 Bits
• 1 “Byte”
• 2 Hex Digits = 256 things

​

​

Memorize this table.

Yan, SP25

02-Number Representation (13)

​

Convert Binary -> Hexadecimal

• Binary -> Hex? Easy!
• Left-pad with 0s
• (Group into full 4-bit values)
• Look it up
• 0b11110� → 0b00011110�(→ 0b0001 1110)� → 0x1E

​

• Hex -> Binary? Easy!
• Just look it up
• 0x1E� → 0b00011110� → 0b11110 (drop leading 0s)

• Hex -> Binary? Easy!
• Just look it up
• 0x1E� → 0b00011110� → 0b11110 (drop leading 0s)

Memorize this table.

Yan, SP25

02-Number Representation (14)

​

Which base do we use?

• Decimal: great for humans, especially when doing arithmetic
• Hex: if human looking at long strings of binary numbers, its much easier to convert to hex and see 4 bits/symbol
• Terrible for arithmetic on paper
• Binary: what computers use
• To a computer, numbers are always binary
• Regardless of how number is written:
• 32_ten == 32₁₀ == 0x20 == 100000₂ == 0b100000

​

• To avoid confusion:
• Decimal: subscript “ten” or prefix (none)
• Hex: subscript “hex” or prefix 0x
• Binary: subscript “two” or prefix 0b

Yan, SP25

02-Number Representation (15)

​

The computer knows it, too…

#include <stdio.h>

int main() {

const int N = 1234;

printf("Decimal: %d\n",N);

printf("Hex: %x\n",N);

printf("Octal: %o\n",N);

​

printf("Literals (not supported by all compilers):\n");

printf("0x4d2 = %d (hex)\n", 0x4d2);

printf("0b10011010010 = %d (binary)\n", 0b10011010010);

printf("02322 = %d (octal, prefix 0 - zero)\n", 0x4d2);

return 0;

}

Output Decimal: 1234

Hex: 4d2

Octal: 2322

Literals (not supported by all compilers):

0x4d2 = 1234 (hex)

0b10011010010 = 1234 (binary)

02322 = 1234 (octal, prefix 0 - zero)

(more next time)

Yan, SP25

02-Number Representation (16)

​

Pop quiz??

1011

1. How many “things” can be represented by 4 bits?

​

​

• [no pollEV, just discuss] How many bits do you need to represent π (pi)?

​

​

• [no pollEV, just discuss] What does this particular 4-bit pattern represent?

A. 4 C. 16

B. 8 D. 64

E. Something else

A. 1

B. 9 (π=3.14, so 0.011”.” 001100)

C. 64 (Macs are 64-bit machines)

D. Every bit the machine has

E. ∞

Yan, SP25

02-Number Representation (17)

​

Yan, SP25

02-Number Representation (18)

​

Pop quiz??

1011

• How many “things” can be represented by 4 bits?

​

​

• [no pollEV, just discuss] How many bits do you need to represent π (pi)?

​

​

• [no pollEV, just discuss] What does this particular 4-bit pattern represent?

A. 4 C. 16

B. 8 D. 64

E. Something else

A. 1

B. 9 (π=3.14, so 0.011”.” 001100)

C. 64 (Macs are 64-bit machines)

D. Every bit the machine has

E. ∞

Yan, SP25

02-Number Representation (19)

​

BIG IDEA: Bits can represent anything!!

• Logical values? 1 bit
• One possible convention: 0 → False, 1 → True

• Characters? Several options:
• A, …, Z: 26 letters → 5 bits (25 = 32)
• ASCII: upper/lower case + punctuation → 7 bits → round to 1 byte
• Unicode (www.unicode.com): standard code to cover all the world’s languages ⇒ 8, 16, 32 bits

• Colors?
• HTML color codes: 24 bits (3 bytes)
• Locations / addresses?�Commands?
• IPv4 (32 bit), IPv6 (64 bit), etc.

With N bits, you can represent at most 2^N things.

Yan, SP25

02-Number Representation (20)

​

Integer Representations

Agenda

• Binary, Decimal, Hex
• Integer Representations
• Sign-Magnitude,�Ones’ Complement
• Two’s Complement
• Bias Encoding

Yan, SP25

02-Number Representation (21)

​

How do we pick a representation for integers?

• Want a representation that supports common integer operations:
• Add them
• Subtract them

• Example: 10 + 7 = 17
• 10, 7 can be represented with 4 bits:
• Addition, subtraction just as you would in decimal!!
• So simple to add in binary that we can build circuits to do it!
• This design decision would make hardware simple!
• …wait…

1010

+ 0111

• Multiply them
• Divide them

• Compare them�(<, =, ≠, ≤, etc.)

10001

Yan, SP25

02-Number Representation (22)

​

What if “too big”? Overflow

• Strictly speaking, base 2 numerals have an ∞ number of digits.
• With almost all being same (00…0 or 11…1) except rightmost digits
• Just don’t normally show leading digits

​

• However, hardware has physical limits. No infinite bits!
• Common representations: 8 bits, 16 bits, 32 bits, 64 bits, …
• Again: With N bits, you can represent at most 2^N things.

• If integer result of operation (+, -, *, /, >, <, =, etc.) cannot be represented by HW bits, we say integer overflow occurred

Integer overflow: The arithmetic result is outside the representable range.

…00000001010

Yan, SP25

02-Number Representation (23)

​

Many Possible Number Representations

• What about signed numbers? Need a way to represent negative numbers. Let’s discuss a few:
• Sign-Magnitude
• Ones’ Complement
• Two’s Complement (C23: the only signed integer rep permitted)
• Bias Encoding (if time, otherwise review on your own)

• So far, we have only discussed unsigned numbers (non-negative).
• C’s uint8_t, uint16_t, etc.: [0, 2^N-1]
• Most computers use the “obvious” representation:

0

1

2^N-2

2^N-1

Yan, SP25

02-Number Representation (24)

​

Sign-Magnitude, Ones’ Complement

Agenda

• Binary, Decimal, Hex
• Integer Representations
• Sign-Magnitude,�Ones’ Complement
• Two’s Complement
• Bias Encoding

Yan, SP25

02-Number Representation (25)

​

Sign-Magnitude: Ain’t no free lunch

• Strawman (“obvious”) solution:
• Leftmost sign bit: 0 → +, 1 → –

• Sign-magnitude is rarely used, due to many shortcomings:
• Incrementing “binary odometer” increases values sometimes, decreases values other times
• Arithmetic circuit complicated: special steps depending on if signs are same/different
• Two zeros (how to compare??)
• Reasonable for signal processing,�not for general purpose computers

0x00000000 = +0_ten

0x80000000 = –0_ten

• Rest of bits: numerical value

Yan, SP25

02-Number Representation (26)

​

Ones’ Complement: Another try

• To represent a negative number, complement (“flip”) the bits of its positive representation:

• Observations:
• Positive numbers: leading 0s
• Negative numbers: leading 1s

• #s represented in N bits:
• Zero: 2
• Positive: (2^N)/2 - 1
• Negative: (same as positive)

0b 1111 1000

-7_ten =

+7_ten = 0b 0000 0111

Yan, SP25

02-Number Representation (27)

​

Shortcomings of Ones’ Complement?

• Advantages:
• Leftmost bit (“most significant bit”) is still effectively sign bit
• Incrementing binary odometer consistent on the representable # line

​

• Some disadvantages still persist:
• Still two zeros
• Arithmetic still somewhat complicated (more later)
• While used for a while on some computer products
• Incrementing binary odometer consistent on the representable # line

​

Yan, SP25

02-Number Representation (28)

​

Two’s Complement

Agenda

• Binary, Decimal, Hex
• Integer Representations
• Sign-Magnitude,�Ones’ Complement
• Two’s Complement
• Bias Encoding

Yan, SP25

02-Number Representation (29)

​

Two’s Complement: C23 standard number rep.

• Ones’ complement:

​

​

​

• The problem: Negative mappings “overlap” with the positive ones, creating the two 0s.

• The solution: Shift the negative mappings left by one.

Yan, SP25

02-Number Representation (30)

​

Arithmetic in Two’s Complement is simple

• Advantages:
• Leftmost bit (“most significant bit”) is still effectively sign bit
• Incrementing binary odometer consistent on the representable # line
• One zero
• Simple hardware for addition

5

+ -5

0

Decimal

Yan, SP25

02-Number Representation (31)

​

Arithmetic in Two’s Complement is simple

• Advantages:
• Leftmost bit (“most significant bit”) is still effectively sign bit
• Incrementing binary odometer consistent on the representable # line
• One zero
• Simple hardware for addition

5

+ -5

0

Decimal

1

dropped

Yan, SP25

02-Number Representation (32)

​

Two’s Complement: Formula

0b0101

= (0 x –2³) + (1 x 2²) + (0 x 2¹) + (1 x 2⁰)

= 0 + 4 + 0 + 1

= 5

0b1011

= (1 x –2³) + (0 x 2²) + (1 x 2¹) + (1 x 2⁰)

= -8 + 0 + 2 + 1

= -5

• Positive and negative numbers can be computed using the same formula:
• Bit values multiplied by powers of 2!!!

Yan, SP25

02-Number Representation (33)

​

Two’s Complement: Algorithm

0b0101

= (0 x –2³) + (1 x 2²) + (0 x 2¹) + (1 x 2⁰)

= 0 + 4 + 0 + 1

= 5

0b1011

= (1 x –2³) + (0 x 2²) + (1 x 2¹) + (1 x 2⁰)

= -8 + 0 + 2 + 1

= -5

• Positive and negative numbers can be computed using the same formula:
• Bit values multiplied by powers of 2!!!

• Hardware to convert positive to negative (& vice versa) is simple.
• Complement all bits
• Then add 1

At home: Prove algorithm is equivalent to formula!

Yan, SP25

02-Number Representation (34)

​

Two’s Complement: C standard (as of 2024)

• Two’s complement is the C23 standard number representation for signed integers.

​

​

• 2^(N-1) negatives
• 2^(N-1) non-negatives
• 1 zero
• How many positives?

[READ AT HOME]

Yan, SP25

02-Number Representation (35)

​

Two’s Complement: Integer Overflow

• Two’s complement is the C23 standard number representation for signed integers.

​

​

• 2^(N-1) negatives
• 2^(N-1) non-negatives
• 1 zero
• How many positives?

• Integer overflow in two’s complement can be conceptualized via a “number wheel”:

⚠️

⚠️

⚠️

[READ AT HOME]

Yan, SP25

02-Number Representation (36)

​

And in summary…

• We represent “things” in computers as particular bit patterns:
• With N bits, you can represent at most 2^N things.
• Today, we discussed five different encodings for integers:
• Unsigned integers
• Signed integers:
• Sign-Magnitude
• Ones’ Complement
• Two’s Complement
• Bias Encoding (**for you to learn at home)
• Computer architects make design decisions to make HW simple
• Two’s complement is the C standard. Learn it!!
• Integer overflow: The result of an arithmetic operation is outside the representable range of integers.
• Numbers have infinite digits, but computers have finite precision. This can lead to arithmetic errors. More later!

[READ AT HOME]

Yan, SP25

02-Number Representation (37)

​

Bias Encoding

[READ AT HOME]

Agenda

• Binary, Decimal, Hex
• Integer Representations
• Sign-Magnitude,�Ones’ Complement
• Two’s Complement
• Bias Encoding

Yan, SP25

02-Number Representation (38)

​

Bias Encoding

• We have a system�that can represent this:

​

• We want to represent this:

​

• Bias encoding: “Shift” the numbers so that they center on zero

​

• Formally:
• Define a “bias”
• To interpret stored binary: Read the data as an unsigned number, then add the bias
• To store a data value: Subtract the bias, then store the resulting number as an unsigned number

39

[READ AT HOME]

Yan, SP25

02-Number Representation (39)

​

Bias Encoding: N = 4, bias = -7

• N-bit representation:
• bias: chosen as -(2^N-1 - 1)�we’ll generally tell you on exams
• Number = (unsigned rep) + (bias)
• Consider:
• One zero
• How many positives?
• How many negatives?

Example: N = 4, bias = -7

[READ AT HOME]

Update 1/27; see Ed

Yan, SP25

02-Number Representation (40)

​

Yan, SP25

02-Number Representation (41)

​

Yan, SP25

02-Number Representation (42)

​

Yan, SP25

02-Number Representation (43)

​