Computing 104: Integer Addition and Subtraction Mystery Cache
Computing 104: Integer Addition and Subtraction
Please note Use of geocaching.com services is subject to the terms and conditions
in our disclaimer.
There is absolutely nothing wrong with the coordinates above. I'm sure they would take you to a very nice location where you could enjoy God's creation. However, if you want to find this cache, I don't recommend going there; I recommend solving the puzzle instead.
Good morning, class! Today we're going to look at how computers do integer arithmetic. To understand today's material you will need to know about binary, binary math, and Boolean equations from our previous classes: GC4A8Z8, GC4AEKD, and GC4BCX2. During class today we will be taking another quiz, and the answers to the quiz will fill in the numbers for North A BC.DEF West G HI.JKL
Let's review for a minute. If we add two binary numbers together, we sometimes get a carry out of a particular column. Note the carries below:
c c
0 0 1
0 1 1
1 0 0
OK, time for another question. What is the sum of 011010 + 001101? Use this number as A.
Remember, in binary the only values are 0 and 1. Thus, in the rightmost column (least significant bit or LSB) we are adding 2 digits which can only be 0 or 1. However, in all other columns, we are adding 3 digits (two, plus the carry). We are going to look at how the computer adds binary numbers, so we see that the computer actually needs different hardware to do the LSB than for the others. Let's examine the LSB first. Since there are only 2 digits being added, the sum can only be 0, 1, or 2. Note: if the sum is 2, then the sum is actually 0, with a carry to the next column to the left. This is the only situation when there will be a carry. So, for the LSB, we have 2 bits being added, and we have two result bits: the sum and the carry. Both the sum and the carry will be either 0 or 1. First, let's develop a Boolean equation for the carry bit.
Quiz time! When do we get a carry of 1? Use the index of the answer for B.
2. When neither input is 1.
3. When 1 of the inputs is 1.
4. When both inputs are 1.
5. Never.
Think about the result you got from the previous quiz. Assume the two inputs to the LSB are a and b. What is the Boolean equation for the carry result? Use the index of the answer for C.
2. carry = a
3. carry = a ^ b
4. carry = a + b
5. carry = ab
Remember, the Boolean equation simply tells us how to hook up logic gates (i.e., hardware made from transistors), so now we know what gates are required to make the carry bit for the LSB of an adder. BTW, we call the hardware piece we are building with 2 inputs, a sum, and a carry a half-adder. We are halfway toward designing one. Now we need to figure out the sum output of the half-adder. When will the sum bit be a 1? Ahhh ... when exactly 1 of the inputs is 1. See that? Of course you don't see that sciwiz1. If you did, your name would be "mathwiz1." If neither is 1, then sum = 0. If both are 1, we get a carry and a sum of 0. Got it? Ok, let's develop a Boolean equation.
What is the Boolean equation for the sum result of a half-adder? Use the index of the answer for D.
4. sum = ab
5. sum= ~ab
6. sum = ~ba
7. sum = ~ab + ~ba
8. sum = a + b
See, that wasn't half-bad. Get it ... half-bad for the half adder? Ok ... rough crowd. Let's move on to the full adder. A full adder is used to do addition of every bit except for the LSB. We already saw that a full adder has 3 inputs: a, b, and cin (carry in). It has two outputs: sum and carry.
So, with 3 inputs, the result will be 0-3. Let's think about the carry first again. We carry when the sum is 2 or 3.
When do we get a carry of 1 from the full adder? Use the index of the answer for E.
5. When none of the inputs is 1.
6. When 1 of the inputs is 1.
7. When 2 or more of the inputs are 1.
8. Never.
Think about the result you got from the previous quiz. Assume the three inputs to the full adder are a, b, and c (for carry in). What is the Boolean equation for the carry result? Use the index of the answer for F.
0. carry = ab + bc
1. carry = ab + bc + ac
2. carry = abc
3. carry = abc + ~abc
4. carry = ~ab + ~cb + a
Let's have an easy quiz question:
3 inputs is a full adder. 2 inputs is a half-adder. What do we call a device that adds 1 input? Use the index of the answer for G.
15. A double adder.
39. A quarter adder.
84. Gimme a break! How can you add with only 1 input?
So, now we arrive at the sum output of the full adder.
Quiz time! When is the sum output equal 1? Use the index of the answer for H.
0. When 1 or 3 of the inputs is 1.
1. When none of the inputs is 1.
2. When 1 of the inputs is 1.
3. When 2 or more of the inputs are 1.
4. Never.
Think about the result you got from the previous quiz. Assume the three inputs to the full adder are a, b, and c (for carry in). What is the Boolean equation for the sum result? Use the index of the answer for I.
0. sum = ab + bc + ac
1. sum = ab + ~bc + ac
2. sum = (a ^ b) + bc
3. sum = a ^ b ^ c
4. sum = a + b + c
Ok, who has a headache? Tough! So, now we see how to make full adders and half-adders. With these tools, the computer can add 32-bit or 64-bit numbers. Yes, texasdevils, in Texas they could do 256-bit numbers; we know everything's bigger in Texas. We just array a half-adder with a series of full adders, as shown below (pictured is an 8-bit adder). If we array 31 full adders with one half-adder, we will get 32 sum outputs ... which is the result of adding two 32-bit numbers! Pretty cool, huh?
Well, we still have a few minor problems. We've designed an adder that only adds positive integers. How does a computer handle negative integers? Well, one simple solution is a sign bit. If 0011 is a binary 3, then let's use the most significant bit (MSB) as the sign bit. So, 1011 is a -3, and 0011 is a 3. Works pretty well, but what happens if we add a -3 and a 3 using the hardware we've been developing? 1011 + 0011 = 1110, which is a -6. Not quite the result we were looking for. So, this representation of negative integers has issues. Another problem it has is that 0000 and 1000 both represent zero, which can cause confusion.
So, another representation for negative integers, which is actually the one used in virtually all computers, is two's complement. This is a really awesome approach that allows addition to be done on positive and negative integers using the full and half-adders we've already developed. To turn a positive integer into a negative integer of the same magnitude, we simply complement all of the bits, and then add 1. When we say complement, we simply mean change all the 0's to 1's, and vice versa. So if we have a 0011 (a 3), first we invert all the bits and get 1100. Then we add 1, and get 1101. Simple? I see you are shaking your heads "no." Well, there's a reason we use this somewhat complicated representation. Watch what happens when we add -3 and 3. 1101 + 0011 = 0000. Ahhh, that's a better answer! 0, janata, the answer was 0. So, remember: complement all the bits then add 1. BTW, you can go from negative to positive the same way. If 1101 is -3: let's complement and get 0010, then add 1 and get 0011. See, it works!
Let's see if you've got it. Which if the following is the two's complement representation of -21? Use the index of the answer for J.
4. 11111111
5. 11101011
6. 01010101
7. 11101010
8. 11001011
9. None of the above.
What is the integer value of the result of adding 00010111 + 11100101? Use the index of the answer for K.
4. 5
5. -12
6. 16
7. -4
8. -3
9. -11
Well, you guys are doing pretty well. But we've got one more topic to explore. How do computers do integer subtraction? Good question! Actually, we employ a little trick which allows us to use the same hardware we discussed above. Let's think first in decimal. What is 7-4? Is that the same as 7 + (-4)? Of course! Yes, TC+12, your name could be TC - (-12). So, what if to do subtraction, we instead add the negative of our number; then we could just use the adder hardware we already have. Would that work? It would if we could just figure out how to take the negative of a number, i.e., convert 4 to -4. Ok, let's think about it in binary. How do we convert a binary number into its negative? We just discussed that: it's called two's complement. So, if we can take the two's complement of a number, and then add it, we've really done subtraction. So, we need some hardware to do two's complement. We want to do 7 - 4, which is 0111 - 0100. Let's assume A = 0111 and B = 0100. Then what we need to do first is invert every bit of B before we put it into the adder. We can do that using inverters. Remember those from our previous lesson? So, each bit of B has to be put through an inverter. But now we need to add 1. Here's the trick: remember that we used a half-adder in the LSB of the adder we developed? We did that because we only had 2 bits to add; there was no carry in like all other bits. What if we instead put a full adder on the LSB, and allow it to have a carry in? When we are doing addition, we simply put a 0 in as the carry in. How would we handle carry in to the LSB for subtraction?
What value would we put into the carry in of the LSB when we want to do subtraction? Use the index of the answer for L.
1. What is subtraction?
2. What is an LSB?
3. 0
4. 1
5. 2
9. Can I be excused to use the rest room?
There is some optimization we can do to make addition and subtraction complete faster, but that is the basic approach for how computers do integer addition and subtraction. Pretty cool, huh? Don't you love this stuff? No Nylimb! It is not "totally tubular." We don't say that in Ohio.
You can validate your puzzle solution with certitude.
Additional Hints
(Decrypt)
Frr, qba'g lbh ybir guvf fghss!
Treasures
You'll collect a digital Treasure from one of these collections when you find and log this geocache:
Loading Treasures