CS136 Winter 2015 - Tutorial 3 CS136 ISAs: [email protected] 27th, 28th of January, 2015 0-0 Goals of this Tutorial The goal of this tutorial is to reinforce the following material: • different systems of numeration (binary, decimal, hexadecimal and octal) • memory capacity • bits, bytes, and chars in memory • overflow • modules in C (testing and interface & implementation files) • working with floats CS 136 Winter 2015 Tutorial 3 1 Systems of Numeration Recall three systems of numeration: binary (base 2), decimal (base 10), and hexadecimal (base 16). We will also introduce one new system of numeration, octal (base 8). When we write the number 97 in decimal, we interpret it as 97 = 9 × 101 + 7 × 100 . We can represent the number 97 in other numerical systems; consider the following alternate represenations of 97: 11000012 , and 6116 . Each base is denoted by a subscript. Conventionally, if a number is in base 10 then it will not have a subscript. CS 136 Winter 2015 Tutorial 3 2 Binary notation In a binary representation (also known as base 2) there are two distinct digits (01). When we write the number 1011010 in binary, we interpret it as 1 × 26 + 0 × 25 + 1 × 24 + 1 × 23 + 0 × 22 + 1 × 21 + 0 × 20 = 64 + 16 + 8 + 2 = 90 (in base 10). 4 binary digits, can represent 24 (16) different possible values (0 . . . 1111) or (0 . . . 15) in base 10. In CS 251 / CS 230 you will learn more about binary notation. CS 136 Winter 2015 Tutorial 3 3 Hexadecimal notation In a hexadecimal (hex) representation (also known as base 16) there are sixteen distinct digits (0123456789ABCDEF). When we write the number 2A9F in hex, we interpret it as 2 × 163 + 10 × 162 + 9 × 161 + 15 × 160 = 8192 + 2560 + 144 + 15 = 10911 (in base 10). The reason hex is so popular is because it is easy to switch between binary and hex representation. A single hex digit corresponds to exactly 4 bits. CS 136 Winter 2015 Tutorial 3 4 Conversion table Dec Bin Hex Dec Bin Hex 0 0000 0 8 1000 8 1 0001 1 9 1001 9 2 0010 2 10 1010 A 3 0011 3 11 1011 B 4 0100 4 12 1100 C 5 0101 5 13 1101 D 6 0110 6 14 1110 E 7 0111 7 15 1111 F CS 136 Winter 2015 Tutorial 3 5 Octal In an Octal representation (also known as base 8) there are eight distinct digits (01234567). We write the number 0452 in octal, we interpret it as 4 × 82 + 5 × 81 + 2 × 80 = 256 + 40 + 2 = 298 (in base 10). Consider the following equivalent representations of 97. const int a = 0141; // base 8. const int b = 97; // base 10. const int c = 0x61; // base 16. Be careful, 0141, 0x141 and 141 are not the same! CS 136 Winter 2015 Tutorial 3 6 CQ 1: You are Bart from the Simpsons (a tv show that had its debut in 1989). In the Simpsons each character has four fingers on each hand (total of 8 fingers). If Bart created his own numerical system, it would likely be in base 8. Represent 85 in base 8. 0105 0414 0232 D 0125 E 0101 A B C CS 136 Winter 2015 Tutorial 3 6 Memory Capacity To have a better understanding of the C memory model, we provide a brief introduction to working with bits and bytes. You are probably aware that internally, computers work with bits. A bit of storage (in the memory of a computer) is in one of two states: either 0 or 1. A traditional light switch can be thought of as a bit of storage. CS 136 Winter 2015 Tutorial 3 7 Early in computing it became obvious that working with individual bits was tedious and inefficient. It was decided to work with 8 bits of storage at a time, and a group of 8 bits became known as a byte. Each byte in memory is in one of 256 possible states. With today’s computers, we can have large memory capacities: • 1 KB = 1 kilobyte = 1024 (210 ) bytes∗ • 1 MB = 1 megabyte = 1024 KB = 1,048,576 (220 ) bytes∗ • 1 GB = 1 gigabyte = 1024 MB = 1,073,741,824 (230 ) bytes∗ CS 136 Winter 2015 Tutorial 3 8 ∗ The size of a kilobyte can be 1000 bytes or 1024 bytes, depending on the context. Similarly, a megabyte can be 106 or 220 bytes, etc.. Manufacturers often use the measurement that makes their product appear better. For example, A terabyte (TB) drive is almost always 1012 bytes instead of 240 . To avoid confusion in scientific use, a standard was established to use KB for 1000 bytes and KiB for 1024 bytes, etc.. In general use, KB is still commonly used to represent both. CS 136 Winter 2015 Tutorial 3 9 Primary Memory Modern computers have primary memory in addition to secondary storage (hard drives, solid state drives, flash drives, DVDs, etc.). The characteristics of primary memory and secondary storage devices vary, but in general: Primary Memory: Secondary Storage: • very fast (nanoseconds) • (≈20x-1000x) slower • medium capacity (≈GB) • large capacity (≈TB) • high cost ($) per byte • low cost ($) per byte • harder to remove • removable or portable • erased on power down • persistent after power down CS 136 Winter 2015 Tutorial 3 10 In practice, programs can only “run” in primary memory. When you “launch” a program, it is copied from secondary storage to primary memory before it is “run”. In this course, we are always referring to primary memory, which is also known as Random Access Memory (RAM). With RAM you can access any individual byte directly and you can access the memory in any order you desire (randomly). CS 136 Winter 2015 Tutorial 3 11 Traditional secondary storage devices (hard drives) are faster if you access data sequentially (not randomly). Primary memory became known as RAM to distinguish it from sequential access devices. The term “RAM” is becoming outdated, as solid state drives and flash drives use random access. Also, modern RAM can be faster when accessed sequentially (in “bursts”). Regardless, when you encounter the term “RAM”, you should interpret it as “primary memory” . CS 136 Winter 2015 Tutorial 3 12 Bits, Bytes, and C Characters in Memory Recall that in C, single quotes (') are used to indicate an ASCII character. Moreover, in C there is no difference between the following two variables: const char letter_a = 'a'; const char ninety_seven = 97; In memory, letter_a is represented in 0s and 1s. Recall that there are 8 bits in a byte and a char reserves 1 byte in our RunC environment. CS 136 Winter 2015 Tutorial 3 13 CQ 2: Consider the following definition for i. const int i = 'b'; // equivalent to 98 in decimal. How many bytes does i reserve on the stack and how many 1s (bits) are in the binary representation of i? A B C D E 4 bytes and 1 bit 4 bytes and 2 bits 4 bytes and 3 bits 4 bytes and 4 bits 1 byte and 3 bits CS 136 Winter 2015 Tutorial 3 13 Overflow and Underflow Recall that integer overflow (or underflow) occurs when we try to represent values outside of the integer limits. By carefully specifying the order of operations you can sometimes avoid overflow. If you #include <limits.h>, the constants INT_MIN and INT_MAX are defined with those limit values. CS 136 Winter 2015 Tutorial 3 14 example: overflow k! . Consider the equation m! (1)(2)(3)...(k−2)(k−1)(k) We can express the former equation as (1)(2)(3)...(m−2)(m−1)(m) . If we let k = 13 and m = 10 then (1)(2)...(9)(10) 1 13! = (11)(12)(13) = (1716) = 1716 10! (1)(2)...(9)(10) 1 k! may overflow for sufficiently large values of k , however if we simplify the expression before we evaluate the factorial then we can mitigate overflow. CS 136 Winter 2015 Tutorial 3 15 Modules in C Recall that a C module consists of an interface (.h file) and an implementation (.c file) file. The interface consists of: function declarations, variable declarations, and structure definitions; whereas the implementation consists of variable and function definitions. If a function is declared in the interface then the design recipe goes in the interface with the function declaration, otherwise it goes with the function definition in the implementation file. From assignment 03 onward, you are expected to assert your required restrictions. CS 136 Winter 2015 Tutorial 3 16 example: safe overflow module The CS136 C master has promoted you to project lead for project Safe Overflow. This responsibility entails writing a C module which provides a function that safely determines if the sum of two integers will overflow. Fortunately, the previous project lead wrote some of the interface and implementation; it is your task to finish writing the interface and implementation. CS 136 Winter 2015 Tutorial 3 17 example: test module for the safe overflow module Great work, you have completed the C module; the CS136 C master is pleased. Oops! The CS136 C master noticed that you did not submit your test module. The CS136 C master is asking you to write a test module that verifies the correctness of your module. Write the test module and send it to the CS136 C master. CS 136 Winter 2015 Tutorial 3 18 Working with Floats Consider a bank account with 1 billion dollars and 0 cents; observe what happens when we withdraw $100. const float balance = 1000000000.0; const float withdraw = 100.0; const float new_balance = balance - withdraw; printf("balance = %f\n", balance); printf("withdraw = %f\n", withdraw); printf("new balance = %f\n", new_balance); balance = 1000000000.0 withdraw = 100.0 new balance = 999999872.000000 CS 136 Winter 2015 Tutorial 3 19 CQ 3: From the previous example, the new balance is not accurate because: A floats are stored in memory B one billion is outside the range of a float C floats have a mantissa and an exponent D floats are not precise CS 136 Winter 2015 Tutorial 3 19 It is dangerous to compare floats using the equality operator (==). Typically, we only want to know if a float is within some small distance (i.e. an epsilon) of another float. Bad Good const float a = 10.0/3.0; const float b = 3.333333; const float a = 10.0/3.0; const float b = 3.333333; const float epsilon = 0.000001; printf("a = %f\n", a); printf("b = %f\n", b); printf("a = %f\n", a); printf("b = %f\n", b); assert(a == b); // failed. a = 3.333333 b = 3.333333 Program finished with errors CS 136 Winter 2015 assert((a - b) <= epsilon); assert((a - b) >= -epsilon); a = 3.333333 b = 3.333333 Tutorial 3 20

© Copyright 2017