Report

Binary Arithmetic Outline • • • • • 1 Binary Addition 2’s complement Binary Subtraction Half Adder Logisim Binary Addition • How to add two binary numbers? • Single bit: 0 +0 0 0 +1 1 1 +0 1 1 +1 10 carry bit 2 Binary Addition • What is a carry bit? • Same idea as “carry the 1” in decimal arithmetic: 13 +9 3 10 13 +9 2 10 13 +9 22 Binary Addition • carry bit gets “carried over” to the next bit (to the left..) • Just like decimal addition 0 +0 0 0 +1 1 1 +0 1 1 +1 10 carry bit 4 Binary Addition • Example #1 0100 0011 + 0000 1010 5 Binary Addition • Example #1 carry bit 0100 0011 + 0000 1010 0100 1101 6 Binary Addition • Example #1 • You can always check your work by converting to decimal 0100 0011 + 0000 1010 0100 1101 7 67 + 10 77 Binary Addition • Example #2 1100 0110 + 0100 1010 8 Binary Addition • Example #2 1001 1100 1100 0110 + 0100 1010 1 0001 0000 9th bit!?! 9 Binary Addition • Example #2 • If we must store the answer in a single byte, 9th bit gets ignored… • This is known as overflow 1100 0110 + 0100 1010 1 0001 0000 10 Binary Addition • Example #2 1100 0110 + 0100 1010 1 0001 0000 198 + 74 16 16 !?! Shouldn’t the answer be 272? 11 Binary Addition • What’s the largest number that can be stored in 8-bits? 1111 1111 12 ??? Binary Addition • What’s the largest number that can be stored in 8-bits? 1111 1111 • 272 is greater than 255 • 272 cannot be represented using 8 bits • Has this ever happened to you? 13 255 Outline • • • • • 14 Binary Addition 2’s complement Binary Subtraction Half Adder Logisim 2’s Complement • 8-bits can be used to represent numbers between 0 and 255 • How do we represent negative numbers in binary? • Drumroll…. 2’s complement!! • Makes addition, subtraction, multiplication easier • Most common way to represent signed numbers • Signed: positive AND negative numbers • And no, it’s not 2’s compliment • “Hey 2, your hair looks nice today..” 15 2’s Complement • In 2’s complement system, the leftmost bit indicates the sign • 0 for positive • 1 for negative • When the leftmost bit is 0, the remaining bits are interpreted as before • 0000 0001 => 1 • 0111 1111 => 127 16 2’s Complement • When the leftmost bit is 1, we do the following to obtain the signed decimal representation: 1. 2. 3. 4. 17 Complement (invert) the binary digits (0 => 1; 1 => 0) Convert binary digits to decimal number Multiply by -1 Subtract 1 2’s Complement • Example #1: What is the 2’s complement value of 1100 0110? 1100 0110 1. 2. 3. 4. 18 Invert bits: 0011 1001 Convert to decimal: 57 Multiple by -1: -57 Subtract 1: -58 2’s Complement • Example #2: What is the 2’s complement value of 1001 1001? • Your turn! 1001 1001 19 2’s Complement • Example #2: What is the 2’s complement value of 1001 1001? 1001 1001 1. 2. 3. 4. 20 Invert bits: 0110 0110 Convert to decimal: 102 Multiple by -1: -102 Subtract 1: -103 2’s Complement • Decimal to 2’s complement • If the number is positive: 1. 2. leftmost bit is 0 remaining bits identical to unsigned binary number • E.g., Represent the number 97 using 8-bits, 2’s complement 97 21 = 64 + 32 + 1 = 26 + 25 + 20 = 0110 0001 2’s Complement • Decimal to 2’s complement • If decimal number is negative: 1. 2. 3. 4. 22 add 1 multiply by -1 (to create positive number) create binary sequence invert bits 2’s Complement • Example #3: represent -97 using 8-bits, 2’s complement 1. add 1: 2. multiply by -1: 3. get binary: 0000 4. invert bits: 1111 -97 + 1 = -96 -96 × -1 = 96 96 = 0110 -97 => 1001 1111 23 1001 2’s Complement • Example #4: represent -123 using 8-bits, 2’s complement 1. add 1: 2. multiply by -1: 3. get binary: 1010 4. invert bits: 0101 -123 + 1 = -122 -122 × -1 = 122 122 = 0111 -123 => 1000 0101 24 1000 Break Time!!! 25 Outline • • • • • 26 Binary Addition 2’s complement Binary Subtraction Half Adder Logisim Binary Subtraction • To subtract two binary numbers, X – Y, 1. 2. 3. Invert Y => Y’ Add 1 to Y’ Add X + Y’ • We are basically taking the 2’s complement of Y (Y’) before adding it to X 27 Binary Subtraction • Example #5: 1. invert Y 00001010 => 11110101 28 0010 0001 - 0000 1010 2. add 1 to Y’ 11110101 + 00000001 = 11110110 0010 0001 3. add Y’ to X + 1111 0110 1 0001 this 9 bit 1 gets ignored 0111 th Binary Subtraction • It’s always good to verify your work… 0010 0001 - 0000 1010 0001 0111 29 33 - 10 23 Binary Subtraction • Example #6 0001 1001 - 1110 0010 30 Binary Subtraction • Example #6 1. invert Y 1110 0010 => 0001 1101 0001 1001 - 1110 0010 2. add 1 to Y’ 0001 1101 + 0000 0001 = 0001 1110 3. add Y’ to X 31 0001 1001 + 0001 1110 0011 0111 Binary Subtraction • Verify… 0001 1001 - 1110 0010 0011 0111 32 25 - -30 55 Outline • • • • • 33 Binary Addition 2’s complement Binary Subtraction Half Adder Logisim Half Adder • Can use logic gates to construct adder circuit • Circuit is capable of binary addition • Half Adder has two inputs (A, B) and two outputs (S, C) • S: sum • C: carry A B 34 S Half Adder C Half Adder • Truth table for Half Adder S : sum of A + B A B S C C : carry bit 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 A B 35 S Half Adder C Half Adder • Logic gate circuit for Half Adder? • A, B inputs • S, C outputs A B S C 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 36 Half Adder • Logic gate circuit for Half Adder? • A, B inputs • S, C outputs A B S C 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 37 Half Adder • How would you expand the Half Adder to create a: • • • • 2-bit adder? 4-bit adder? 8-bit adder? …? • This will be part of your homework… 38 Outline • • • • • 39 Binary Addition 2’s complement Binary Subtraction Half Adder Logisim Logisim • Logisim is FREE logic gate simulation software • Please download / install this software • http://www.cburch.com/logisim/index.html • It should be on the lab machines, too 40 Next Steps • Download / install Logisim • Complete homework #2 • Data representation • Binary arithmetic • Create (useful) logic gate circuits using Logisim • Next lecture: Micro-architecture 41