A few interesting things I learned so far this semester
Some of you are going to be all like pfft, I already knew about it or figured it out myself, but for the rest of you, here's something I think is totally awesome, that I only became aware of this week (due to a friend who likes to pose these problems to me while I drive, which is exactly when I most strongly shouldn't be thinking about them, if that makes any sense). The beauty of it is in the simplicity.
Say you need to swap variables A and B. You could just make variable C and say: Put the value of B in C, then put the value of A in B, and then put the value of C in A.
A= 1, B =2, C (empty)
2 -> C
1 -> B
2 -> A
So now they are swapped, but you had to use an extra variable to store a value. That's kind of wasteful, so you could try this:
A = A+B ( which is 3)
B = A - B (which is 2)
A= A - B (which is 1)
But if you're constrained to a number of digits to represent a number, you could experience overflow. For example, working in our regular old base ten number system and allotting each value only one digit of memory, if you had to add an A = 6 with B= 5 you would end up with 11, which can't be represented in base ten with one digit. In binary, if you allot 3 bits to your numbers, you can't represent 8 (7 is 111, 8 is 1000).
In binary, using boolean logic, you can do this swap without risking overflow AND without using another variable. The trick is XOR. In case you aren't familiar with boolean logic:
OR will evaluate to true with either input is true, or both are true. Let 1 represent true, 0 represent false:
A B (A OR B)
0 0 0
1 0 1
0 1 1
1 1 1
For example, if my alarm is ringing OR the time is already 9am, I need to get up. If both are true, I need to get up. If only one of the two conditions is true, I still need to get up. The only time I don't have to get up is if it isn't yet 9am, and my alarm isn't ringing.
XOR is similar. It stands for Exclusively Or. The difference is that for XOR, if both conditions are true, A XOR B does not evaluate to true. So...
A B (A XOR B)
0 0 0
1 0 1
0 1 1
1 1 0
So again, exactly like OR, but now 1 xor 1 evaluates to 0.
So now the binary swap (note this works only in binary, but you can use it to swap binary representations of numbers with values higher than 1)
A = A xor B
B = A xor B
A = A xor B
Super simple. Let's try it out (you can try it out on all four cases, but I'll just do one) on A = 1, B = 0
A = 1 xor 0 = 1
B = 1 xor 0 = 1
A = 1 xor 1 = 0
So from A = 1, B = 0 we go to A = 0, B = 1. Sooo easy!
On a last note: If in binary A is equal to 1111, then the bitflip is 0000. So the bitflip is defined by just switching ones for zeroes and zeroes for ones. As it turns out, if you're doing addition/subtraction in binary:
(A - B) = A + the bitflip of B + 1, dropping the carryout from the most significant bit
It's easier than subtraction in decimal. I've actually forgotten how to properly carry numbers over, I always screw something up. But since binary subtraction is better expressed as binary addition, then I find it easy.
And now, for Physics homework, and then 8 am physics lab....Hope you found any of that interesting!
Say you need to swap variables A and B. You could just make variable C and say: Put the value of B in C, then put the value of A in B, and then put the value of C in A.
A= 1, B =2, C (empty)
2 -> C
1 -> B
2 -> A
So now they are swapped, but you had to use an extra variable to store a value. That's kind of wasteful, so you could try this:
A = A+B ( which is 3)
B = A - B (which is 2)
A= A - B (which is 1)
But if you're constrained to a number of digits to represent a number, you could experience overflow. For example, working in our regular old base ten number system and allotting each value only one digit of memory, if you had to add an A = 6 with B= 5 you would end up with 11, which can't be represented in base ten with one digit. In binary, if you allot 3 bits to your numbers, you can't represent 8 (7 is 111, 8 is 1000).
In binary, using boolean logic, you can do this swap without risking overflow AND without using another variable. The trick is XOR. In case you aren't familiar with boolean logic:
OR will evaluate to true with either input is true, or both are true. Let 1 represent true, 0 represent false:
A B (A OR B)
0 0 0
1 0 1
0 1 1
1 1 1
For example, if my alarm is ringing OR the time is already 9am, I need to get up. If both are true, I need to get up. If only one of the two conditions is true, I still need to get up. The only time I don't have to get up is if it isn't yet 9am, and my alarm isn't ringing.
XOR is similar. It stands for Exclusively Or. The difference is that for XOR, if both conditions are true, A XOR B does not evaluate to true. So...
A B (A XOR B)
0 0 0
1 0 1
0 1 1
1 1 0
So again, exactly like OR, but now 1 xor 1 evaluates to 0.
So now the binary swap (note this works only in binary, but you can use it to swap binary representations of numbers with values higher than 1)
A = A xor B
B = A xor B
A = A xor B
Super simple. Let's try it out (you can try it out on all four cases, but I'll just do one) on A = 1, B = 0
A = 1 xor 0 = 1
B = 1 xor 0 = 1
A = 1 xor 1 = 0
So from A = 1, B = 0 we go to A = 0, B = 1. Sooo easy!
On a last note: If in binary A is equal to 1111, then the bitflip is 0000. So the bitflip is defined by just switching ones for zeroes and zeroes for ones. As it turns out, if you're doing addition/subtraction in binary:
(A - B) = A + the bitflip of B + 1, dropping the carryout from the most significant bit
It's easier than subtraction in decimal. I've actually forgotten how to properly carry numbers over, I always screw something up. But since binary subtraction is better expressed as binary addition, then I find it easy.
And now, for Physics homework, and then 8 am physics lab....Hope you found any of that interesting!