▶ 目录 ← 首页
CS61C

Summary

And in Summary…\dots

  • We represent “things” in computers as particular bit patterns:
    • With NN bits, you can represent at most 2N2^N things.
  • Today, we discussed five different encodings for integers:
    • Unsigned integers
    • Signed integers:
      • Sign-Magnitude
      • Ones’ Complement
      • Two’s Complement
    • Bias Encoding
  • Computer architects make design decisions to make HW simple
    • Unsigned and Two’s complement are C standard. Learn them!!
  • 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!

Meta takeaway: We make design decisions to make the hardware simple. We threw out sign magnitude and ones’ complement because the hardware would be hard. But here’s a secret: it’s the same hardware for mathematics on unsigned and two’s complement numbers. The only difference is how you calculate overflow.

Textbook Readings

P&H: 2.4

Additional References

Dan Garcia’s Binary Slides, Fall 2025

Amazing Illustrations by Ketrina (Yim) Thompson: CS Illustrated Number Rep Handouts

Exercises

Check your knowledge!

Conceptual Review

Solution

A bit is the smallest unit of digital information and it can be either 0 of 1. There are 4 bits in a nibble and 8 bits in a byte.

Solution

When the result of an arithmetic operation is outside the range of what is representable by given number of bits.

Solution
  • Unsigned: [0,2n−1][0, 2^n-1]
  • Sign-Magnitude: [−(2n−1−1),2n−1−1][-(2^{n-1} - 1), 2^{n-1} - 1]
  • One’s complement: [−(2n−1−1),2n−1−1][-(2^{n-1} - 1), 2^{n-1} - 1]
  • Two’s complement: [−2n−1,2n−1−1][-2^{n-1}, 2^{n-1} - 1]
  • Bias: [0+[0+bias,2n−1+, 2^n-1+bias]]

Solution
  • Unsigned: 1
  • Sign-Magnitude: 2
  • One’s complement: 2
  • Two’s complement: 1
  • Bias: 1 or 0 (depending on bias)

Short Exercises

Solution

True. The same bits can be interpreted in many different ways with the exact same bits! The bits can represent anything from an unsigned number to a signed number or even, as we will cover later, a program. It is all dependent on its agreed upon interpretation.

Solution

False. In Two’s Complement, the MSB is always 1 for a negative number. This means EVERY negative number in Two’s Complement, when converted to unsigned, will be larger than the positive numbers.

Solution

False. Our current representation formats has a major limitation; we can only represent and do arithmetic with integers. To successfully represent fractional values as well as numbers with extremely high magnitude beyond our current boundaries, we need another representation format.

Solution

C.

Solution

7 bits. (116)10=(116)_{10} = 0b111 0100 or log2116≈6.85log{_2}{116} \approx 6.85 which we round to 7 bits.