The Design of C A Rational Reconstruction 1 Goals of this Lecture Help you learn about The decisions that were available to the designers of C The decisions that were made by the designers of C and thereby C Why Learning the design rationale of the C language provides a richer understanding of C itself and might be more interesting than simply learning the language itself A power programmer knows both the programming language and its design rationale But first a preliminary topic 2 1 Preliminary Topic Number Systems 3 Why Bits Binary Digits Computers are built using digital circuits Inputs and outputs can have only two values True high voltage or false low voltage Represented as 1 and 0 Can represent many kinds of information Boolean true or false Numbers 23 79 Characters a z Pixels sounds Internet addresses Can manipulate in many ways Read and write Logical operations Arithmetic 4 2 Base 10 and Base 2 Decimal base 10 Each digit represents a power of 10 4173 4 x 103 1 x 102 7 x 101 3 x 100 Binary base 2 Each bit represents a power of 2 10110 1 x 24 0 x 23 1 x 22 1 x 21 0 x 20 22 Decimal to binary conversion Divide repeatedly by 2 and keep remainders 12 2 6 R 0 6 2 3 R 0 3 2 1 R 1 1 2 0 R 1 Result 1100 5 Writing Bits is Tedious for People Octal base 8 Digits 0 1 7 Hexadecimal base 16 Digits 0 1 9 A B C D E F 0000 0 0001 1 0010 2 0011 3 0100 4 0101 5 0110 6 0111 7 1000 8 1001 9 1010 A 1011 B 1100 C 1101 D 1110 E 1111 F Thus the 16 bit binary number 1011 0010 1010 1001 converted to hex is B2A9 6 3 Representing Colors RGB Three primary colors Red Green Blue Strength 8 bit number for each color e g two hex digits So 24 bits to specify a color In HTML e g course Schedule Web page Red span style color FF0000 De Comment Assignment Due span Blue span style color 0000FF Reading Period span Same thing in digital cameras Each pixel is a mixture of red green and blue 7 Finite Representation of Integers Fixed number of bits in memory Usually 8 16 or 32 bits 1 2 or 4 bytes Unsigned integer No sign bit Always 0 or a positive number All arithmetic is modulo 2n Examples of unsigned integers 00000001 1 00001111 15 00010000 16 00100001 33 11111111 255 8 4 Adding Two Integers From right to left we add each pair of digits We write the sum and add the carry to the next column Base 10 Base 2 0 1 1 0 0 1 2 Sum 1 0 0 1 Carry 0 1 1 1 9 8 2 6 4 Sum 4 6 Carry 0 1 9 Binary Sums and Carries a 0 0 1 1 b 0 1 0 1 Sum 0 1 1 0 a 0 0 1 1 XOR b 0 1 0 1 Carry 0 0 0 1 AND exclusive OR 0100 0101 0110 0111 69 103 1010 1100 172 10 5 Modulo Arithmetic Consider only numbers in a range E g five digit car odometer 0 1 99999 E g eight bit numbers 0 1 255 Roll over when you run out of space E g car odometer goes from 99999 to 0 1 E g eight bit number goes from 255 to 0 1 Adding 2n doesn t change the answer For eight bit number n 8 and 2n 256 E g 37 256 mod 256 is simply 37 This can help us do subtraction Suppose you want to compute a b Note that this equals a 256 1 b 1 11 One s and Two s Complement One s complement flip every bit E g b is 01000101 i e 69 in decimal One s complement is 10111010 That s simply 255 69 Subtracting from 11111111 is easy no carry needed 1111 1111 0100 0101 1011 1010 b one s complement Two s complement Add 1 to the one s complement E g 255 69 1 1011 1011 12 6 Putting it All Together Computing a b Same as a 256 b Same as a 255 b 1 Same as a onesComplement b 1 Same as a twosComplement b Example 172 69 The original number 69 One s complement of 69 Two s complement of 69 Add to the number 172 The sum comes to Equals 103 in decimal 0100 0101 1011 1010 1011 1011 1010 1100 0110 0111 1010 1100 1011 1011 1 0110 0111 13 Signed Integers Sign magnitude representation Use one bit to store the sign Zero for positive number One for negative number Examples E g 0010 1100 44 E g 1010 1100 44 Hard to do arithmetic this way so it is rarely used Complement representation One s complement Flip every bit E g 1101 0011 44 Two s complement Flip every bit then add 1 E g 1101 0100 44 14 7 Overflow Running Out of Room Adding two large integers together Sum might be too large to store in the number of bits available What happens Unsigned integers All arithmetic is modulo arithmetic Sum would just wrap around Signed integers Can get nonsense values Example with 16 bit integers Sum 10000 20000 30000 Result 5536 15 Bitwise Operators AND and OR Bitwise AND Bitwise OR 0 1 0 0 0 0 0 1 0 1 1 1 1 1 0 1 Mod on the cheap E g 53 16 is same as 53 15 53 0 0 1 1 0 1 0 1 15 0 0 0 0 1 1 1 1 5 0 0 0 0 0 1 0 1 16 8 Bitwise Operators Not and XOR One s complement Turns 0 to 1 and 1 to 0 E g set last three bits to 0 x x 7 XOR 0 if both bits are the same 1 if the two bits are different 0 0 1 0 1 1 1 0 17 Bitwise Operators Shift Left Right Shift left Multiply by powers of 2 Shift some of bits to the left filling the blanks with 0 53 0 0 1 1 0 1 0 1 53 2 1 1 0 1 0 1 0 0 Shift right Divide by powers of 2 Shift some of bits to the right For unsigned integer fill in blanks with 0 What about signed negative integers Can vary from one machine to another 53 0 0 1 1 0 1 0 1 53 2 0 0 0 0 1 1 0 1 18 9 Example Counting the 1 s How many 1 bits in a number E g how many 1 bits in the binary representation of 53 0 0 1 1 0 1 0 1 Four 1 bits How to count them Look at one bit at a time Check if that bit is a 1 Increment counter How to look at one bit at a …
View Full Document
Unlocking...