Foundations of Algorithms Workshop 10 === ###### tags: `comp10002` `workshop` `c` --- Discuss Exercises 13.1 and 13.2 Try your hand at Exercise 11.3 --- ### Topics - Data Representation - numerical (binary,octal,hex) - other - File Operations in C --- ### Data representation How do computers represent data? Where does it go? --- ### Data storage (not examinable) - CPU (Registers, L1-L3 Cache) - Memory (people call this RAM - SRAM, DRAM) - Disk (or sometimes cold storage) - SSD (NAND transistor storage in a grid that persists) - Hard Disk (magnetic) - Tape (old but still has a use, magnetic) --- ### Binary Notation How do we represent numbers inside a computer? --- ### What are bits? Bits are the most basic building block for data within the computer. each bit can either be 1 or 0. There are 8 bits in a byte. --- ## Decimal Number System Decimal Number system: 1234 ``` (1 x 1000)+ (2 x 100)+ (3 x 10)+ (4 x l) (1 x 103)+ (2 x 102)+ (3 x 101)+ (4 x l00) 1000 + 200 + 30 + 4 1234 ``` --- ### Binary Number System Base 2: ``` 17 = 16 + 1 = 10000 + 00001 = 10001 ``` --- ``` 34 = ``` --- ### Negative Numbers in Binary System Two's compliment - how all computers represent integers Steps: 1. Write the number in normal binary form 2. Invert Digits 3. Add 1 ``` -17 = 16 + 1 = 10000 + 00001 = 10001 = 0000000000010001 = 1111111111101110 = 1111111111101111 ``` --- ``` -34 = ``` --- ### Addition & Subtraction well, all we really have to do is addition 69 + 12 ``` 1000101 69 0001100 12 ======= 1010001 ``` --- ### Addition & Subtraction well, all we really have to do is addition 69 - 12 == 69 + (-12) ``` 0000 0000 0100 0101 69 1111 1111 1111 0100 -12 ======= 0000 0000 0000 0011 1001 ``` --- ## Integer Types --- ### Characters ```cpp char a = 'a'; // 01100001 == 97 unsigned char a = 'a'; signed char a = 'a'; ``` **Type:** char **Storage Size:** 1 byte (8 bits) **Value Range:** -128 to 127 or (unsigned) 0 to 255 --- ### Ints ```cpp int a = 97; // 00000000000000000000000001100001 unsigned int a = 97; // ``` **Type:** int **Storage Size:** 4 bytes **Value Range:** 0 to 4,294,967,295 (unsigned) **Value Range:** -2,147,483,648 to 2,147,483,647 --- ### Shorts ```cpp short a = 97; // 01100001 == 97 unsigned short a = 97; // 01100001 == 97 ``` **Type:** short **Storage Size:** 2 byte (16 bits) **Value Range:** -32,768 to 32,767 or (unsigned) 0 to 65,535 --- ### Longs ```cpp long a = 97; // 01100001 unsigned long a = 97; // 01100001 ``` **Type:** long **Storage Size:** 8 bytes (64 bits) **Value Range:** -9223372036854775808 to 9223372036854775807 --- ## Hexidecimal Base 16 --- ### Hexidecimal 0,1,2,3,4,5,6,7,8,9, A, B, C, D, E, F 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 17 ``` 17 = 11 34 = 22 ``` --- ### Floating Point Representation Exponents start at 127 (0) if the exponent is 1 then we hae 128 ![](https://i.imgur.com/pDpLaDd.png) --- ### Floating Point Representation Steps: 1. Calculate the number in binary 17.5 = $16 + 1 + 0.5$ = $2^4 + 2^0 + 2^-1$ = $10001.1$ --- ### Floating Point Representation Steps: 2. Shift the binary to the right such that only the leading 1 remains on the left side & count the number of shifts ``` 10001.1 = 10001.1 * 2^0 = 1000.11 * 2^1 = 100.011 * 2^2 = 10.0011 * 2^3 = 1.00011 * 2^4 4 shifts! ``` --- ### Floating Point Representation Steps: 3. Cacluate the number of shifts + 127 as binary (8 bits to work with) ``` 4 + 127 131 = 128 + 2 + 1 = 2^7 + 2^1 + 2^0 = 10000011 ``` --- ### Floating Point Representation Steps: 4. Add it all together and drop the 1 in the mantissa ``` 0 1000 0011 0001 1000 0000 0000 0000 000 sign exponent mantissa (1) (8) (23) ``` --- ### Floating Point Representation -3.125 --- ``` -3.125 = 3.125 = 2 + 1 + .125 = 11.001 (.125 * 2 * 2 * 2) = 1 so 2^3 3 shifts = 1.1001 (1 shift) = 1 (128) 1001 000.... = 1 1000 0000 1001 0000 0000 00000 0000 000 ``` --- ### Floating Point Representation 0.09375 --- ``` 0.09375 = .09375 = .18750 = .37500 = .75000 =1.50000 (2^-4) = 127 - 4 = (64 + 32 + 16 + 8 + 2 + 1) = 0 (123) 1000 0000 0000.... = 0 0111 1011 1000 0000 0000 0000 0000 000 ``` --- ### Floating Point Representation Hexidecimal Floating Point 1. Calculate the number in binary 17.5 = 0 1000 0011 0001 1000 0000 0000 0000 000 --- 2. Group in 4s and calcuate the value in Hexidecimal = 0100 0001 1000 1100 0000 0000 0000 0000 = 4 1 8 12 0 0 0 0 = 4 1 8 C 0 0 0 0 = 418C0000 --- ### Floating Point Representation Hexidecimal Floating Point 1. Calculate the number in binary -3.125 = 1 1000 0000 0010 0000 0000 00000 0000 000 --- 2. Group in 4s and cacluate the value in Hexidecimal = 1100 0000 0100 1000 0000 0000 0000 0000 = 12 0 4 8 0 0 0 0 = C 0 4 8 0 0 0 0 = C0480000 --- ### float ```cpp float a = 97; // 01000010110000100000000000000000 ``` **Type:** float **Storage Size:** 4 bytes (32 bits) **Value Range:** 1.2E-38 to 3.4E+38 **Precision:** 6 decimal places --- ### double ```cpp double a = 97; // ..01000010110000100000000000000000 ``` **Type:** double **Storage Size:** 8 bytes (64 bits) **Value Range:** 2.3E-308 to 1.7E+308 **Precision:** 15 decimal places --- ### Long Double ```cpp long double a = 97; // ..01000010110000100000000000000000 ``` **Type:** long double **Storage Size:** 10 bytes (64 bits) **Value Range:** 3.4E-4932 to 1.1E+4932 **Precision:** 19 decimal places --- ### File Operations `fopen()` `fclose()` `fgets()` `fprintf()` --- ```cpp FILE *fopen (const char *filename, const char *mode) ``` Open and perform operations on a file --- ```cpp int fclose(FILE *fp) ``` closes that file that is being pointed at by the file pointer fp --- ```cpp char *fgets(char *string, int n, FILE *fp) ``` Used to read a file line by line fgets(buffer,size,fp) ---