Quiz 1 Study Guide

Quiz 1 is closed-book and closed-note. No electronic devices are allowed. It includes everything through the floating point lecture. This study guide highlights some of the major topics we have covered so far, but it is not an exhaustive list. Material from lectures and labs but not included here may also appear on the quiz.

Information Storage

• Bits—our first data abstraction
  • 0 and 1 (Represented by some underlying physical property, e.g., voltage)
• Bytes—our first grouping of bits
  • 8 bits make up one byte
  • Important because memory is byte addressable (every byte of data has a unique address in memory)
  • Bytes are the smallest addressable grouping of data in a computer system
• Memory model of a computer
  • Memory can be considered as an large array of bytes
  • A byte of data is located in memory by its address, which is the index into this memory byte array
• Word Size
  • Natural grouping of bits for a given computer architecture
  • Data can be read and written from memory in word-sized chunks
  • Also defines the size of memory addresses (i.e., the size of a pointer is defined by the word size of a system)
  • Modern desktop computers have a word size of 64-bits
• Data Sizes
  • Basic data types are represented in computer systems as a fixed number of bytes
  • In a typical 64-bit system:
    • C integer types: char (1 byte), short (2 bytes), int (4 bytes), long (8)
    • C floating point: float (4 bytes), double (8 bytes)
    • C pointer types: 8 bytes
• Decimal number system
  • Base 10
  • How humans represent numbers
• Binary number system
  • Base 2
  • How computers represent numbers
• Hexadecimal (base-16 numbers)
  • 0-9, A-F represent the numbers 0-15
  • 1 hexadecimal digit represents exactly 4 bits
  • 1 byte is 2 hexadecimal digits
  • Hex is a more compact way of representing numbers than binary
  • Represented in C with a leading 0x in front of the number
• Base-n number systems
  • The weight of each column is n^k where k is the position of the number (starting from 0) and n is the base of the system
• Number conversion
  • Know how to convert numbers to and from decimal, binary, and hexadecimal
  • Know how to convert to and from a decimal number to any base-n system
• Addressing and byte ordering
  • All objects in memory have an address
  • Multi-byte objects are allocated in contiguous memory, increasing from its starting address in one of two conventions, big endian and little endian
  • Big-endian
    • The end byte of the a multi-byte object is at the largest memory address
  • Little-endian
    • The end byte of the a multi-byte object is at the smallest memory address
    • The format RISC-V uses
• Representing strings
  • There is no string type in C
  • Strings are encoded as a null-terminated (\0) array of characters (char)
  • The encoding of characters is typically done in ASCII
• Representing Code
  • Programs written in languages such as C are compiled into assembly code
    • Architecture specific (i.e., RISC-V assembly is different from Arm and Intel x86 assembly)
  • Assembly code is the human readable text form of machine code
    • Assembly code is assembled into machine code
  • Machine code is the sequence of bytes, when loaded into memory by the operating system, that are directly interpreted by the CPU
• Boolean algebra
  • 0 represents False, 1 represents True
  • Bit-level operations: and (&), or (|), xor (^), not (~)
    • Know the truth tables for each of these operations
  • To set a bit to 1: or with 1 (oring with 0 keeps the bit the same)
  • To clear a bit to 0: and with 0 (anding with 1 keeps the bit the same)
  • To flipping a bit: xor with 1 (xoring with 0 keeps the bit the same)
• Logical operations: and (&&), or (||), not (!)
  • There is no boolean type in C
  • Any integer type can be used in a logical operation
  • False is represented by the value 0
  • True is represented by any non-zero number
  • In C, evaluation of logical operations is done lazily
    • For example, if the first expression in a || statement is True the rest of the rest of the expressions will not be evaluated
• Shift operations
  • Left shift: (e.g., x << 2)
    • Zeros will be shifted in to the lsb (least significant bit)
  • Right sifts: (e.g., x >> 2)
    • If x is signed, an arithmetic shift will be done (the sign-bit will be shifted in to the msb)
    • If x is unsigned, a logical shift will be done (a zero will be shifted in to the msb)
  • Shifts < 0 or >= the bit-width are undefined

Integer Representation

• Unsigned numbers
  • Represented as binary numbers in a fixed bit-width for a given type
• Signed two’s complement numbers
  • Asymmetric range (there is one more negative number than positive number)
    • For a k-bit two’s complement number range is (-2^k-1 to 2^k-1-1)
  • Advantages
    • Only one representation of 0
    • Binary arithmetic is the same for signed and unsigned numbers
  • Performing two’s complement negation
    • Flip all the bits and add 1
    • This negates the original number
  • Weight of the MSB is -2^k where k is the bit-width of the two’s complement number
  • The msb acts as sign bit: 1 means the number is negative, 0 means the number is positive
• Conversion between signed an unsigned numbers of the same word size
  • The bits are kept the same and reinterpreted as the new type
  • If the msb is 1 the sign and value of the number will change
• Sign-extension
  • Used when converting from a smaller integer type to a larger integer type
  • The lower bits are kept the same and the upper bits are filled in with the sign-bit (msb) of the original number
  • Value of the number stays the same
• Truncating Numbers
  • Used when converting from a larger integer type to a smaller integer type
  • Extra upper bits will be truncated
  • Remaining lower bits will be reinterpreted as the smaller type
  • Will give exact results if the range of the smaller type can express the original value

Integer Arithmetic

• Unsigned addition
  • May result in overflow if there is a carry out in the msb of the result
  • Equivalent to computing the sum modulo 2^k for a k-bit integer type
  • “Wraps around” zero at most once
• Two’s complement addition
  • May result in positive overflow or negative overflow
  • Positive overflow: when adding two positive numbers results in a negative result
  • Negative overflow: when adding two negative numbers results in a positive result
• Two’s complement negation
  • Taking the two’s complement of a number performs negation on a number
  • Exception: the two’s complement of Tmin is Tmin
• Two’s complement multiplication
  • Mathematically equivalent to calculating the exact product and truncating the result to the lower w-bits for a w-bit numbers
• Multiplying by constants
  • Compiler may replace a multiplication by a constant with a shifts and adds
    • Can be faster on modern hardware
  • A left shift of one is the equivalent to multiplying the number by two
    • In general x << k is equal to x * 2^k (assuming 0 <= k < w for a w-bit number)
• Diving by powers of 2
  • Right arithmetic shifts are the equivalent diving the number by a power of 2
  • With the remainder truncated
  • x >> k yields floor(x/2^k) (assuming 0 <= k < w for a w-bit number)

Floating Point Numbers

• Fractional Binary Numbers
  • Understand how fixed-point binary numbers are represented
• Floating point representation of numbers
  • Numbers are represented in the form V = (-1)^s * M * 2^E where:
    • The sign s is the sign bit, where s = 1 is positive and s = 0 is negative
    • The significand M is a fractional binary number that ranges either between 1 and 2 - ε or between 0 and 1 - ε
    • The exponent E which weights the value by a (possibly negative) power of 2
  • Floating point numbers are divided into three fields that encode the above values
    • The msb directly encodes the sign s
    • The k-bit exponent field exp (which is to the immediate right of the sign bit) encodes E
    • The low order n-bit fraction field frac encodes the significand M
  • Normalized values
    • Most common case, when the exp field is neither all ones or all zeros
    • exp is encodes E via the following: E = e - Bias where exp is an unsigned binary number
    • The Bias is equal to 2^k-1-1
    • M is represented in normalized form, frac is encoded as M with the leading 1. removed (i.e., the fractional part of the normalized number)
  • Denormalized values
    • When the exp field is all zeros
    • Represents zero the numbers closest to zero
    • E = 1 - Bias
    • M is represented in denormalized form, with a leading 0. (instead of a leading 1.), frac is encoded as M with the leading 0. removed (i.e., the fractional part of the denormalized number)
  • NaN and Infinity
    • All ones in the exp field and all zeros in the frac field represents ∞ (infinity)
    • All ones in the exp field and anything other than all zeros in the frac field represents NaN (Not a Number)
• Rounding
  • Round-to-even
    • Round down if number less than half, round up if number is greater than half
    • If half, round in the direction that makes the lsb of the rounded number even
  • Round-towards-zero
    • Always rounds the number to make it closer to zero
    • Rounds down for positive numbers
    • Rounds up for negative numbers
  • Round-down
    • Always makes the number smaller
  • Round-up
    • Always makes the number larger
  • Default rounding mode for floating point is round to even
    • Avoids introducing statistical bias in most real-life situations
• Floating point operations
  • Calculation is performed assuming real numbers and then rounded to fit the floating point type
  • Floating point addition is not associative, due to possible rounding