Simpleton Geek Teaches Computer Programming Book 1 Chapter 4

4. Boolean Logic

4.1 Half full glass

"Gya ha ha ha, what a bunch of losers!" The teacher was looking at the students' papers. How come you're having so much trouble adding two numbers?" Asked him rhetorically.

"But teacher," pleaded Nancy, "The questions are so much harder now. We have to add more than two numbers!"

"So? That's only at the end. The first half is only two numbers, and there's no excuse for you to fail those!"

"Why would you add more numbers to add? It's getting confusing! What is the purpose of making it difficult?"

"Because it's the natural progress of things. You don't want to stuck in the elementary skill level do you? You need to keep progressing so that you can advance to the next level! That's why the only easy day was yesterday! Gya ha ha ha!"

“Now settle down. You all know how to add 2 numbers, no matter the number of digits. In addition to that, you also have the knowledge to multiply 2 numbers in your head. So, all you have to do is expand that knowledge a little bit. Let's say that you have these numbers to add.

9887459323

3248572456

1874965843

6489459454

“So, now what do you do? Go on, add them up.”

The students began by adding 9316 equals 19. Then 8284 equals 22. Write down 21, remember 2. Then add 8478 equals 27. Write down 4. Remember 7. Then …

“Whoa, let me stop you here!” said the teacher. “What do you think you're doing? Adding those numbers like that? You don't do it left to right. You do it right to left! Try again!”

Add 6364 equals 19. Write 9.

Add 12545 equals 17. Write 7.

Add 13484 equals 20. Write 0.

Add 29259 equals 27. Write 7.

Add 25765 equals 25. Write 5.

Add 24594 equals 24. Write 4.

Add 27849 equals 30. Write 0.

Add 38478 equals 30. Write 0.

Add 38284 equals 25. Write 5.

Add 29316 equals 21. Write 21.

“So, the answer is 21500457079. Got it? By going right to left, you only have to remember 1 carry over digit at all times. This way, even when you have to add ten 20 digit numbers together, you'll be fine. Remember, just because geniuses can do the calculation left to right, doesn't mean that you do, too.

“Alright, now let's move on to the next lesson! Tell me this glass of water only filled by half. So you do say that it is half full or half empty?"

"Half full"

"Half empty"

"Gya ha ha ha!" The teacher laughed. "So, which is it? Half full or half empty?"

"It's both."

"In fact, none of you are wrong about it. It is exactly half, therefore you can say that it is half full, or half empty. The point is, that you cannot say that it is NOT half empty when you said that it is half full!

“That's a very important difference, and I hope that you'll never do that, or you're just one of those problematic people.”

4.2 Rabbit/Duck or Young/Old lady
Everybody was seated in their seat. They are writing down furiously. On each paper was a picture of an animal. The students was in their show-and-tell mode, furiously describing the picture.

"Time's up!" The teacher said. "Now let's gather up the paper and reassign your seats." The teacher was reading through the papers really quick. As he spoke their names, he would assign them to left/right side of the class room. The students were all in a confusion. They were all puzzled about this. Why would they be divided by what's written on their paper?
"Okay, is everybody ready?" The class has been neatly divided left and right. "Okay, you start. Just one line, please. What do you see in the picture."
"There is a bill."
The teacher wrote down on the board "a bill".
"Okay, from the other side. What do you see?"
"There an ear."
The students on the left gasped. "Really?" The teacher laughed. He wrote down on the board, "an ear"
"Okay, back to the left. What do you see?"
"There is an eye." The teacher wrote that down as well.
"Next to the right"
"There is fur."
"Fur? Where do you see that?" The students on the left was confused.
"Next to the left."
"There are feathers."
"Feathers? Now you're the one who's blind!" The students on the right was testy.
"Come on, now, no fighting! Let's not accuse anybody of anything." The teacher calmly wrote all the description down. "Next!"
"It floats on water."
"Whaat? Since when rabbits float on water?" The students on the right was confused.
"It's not a rabbit! It's a duck!"
"It certainly is a rabbit!"
"You are wrong! It certainly is a duck!"
"It's a rabbit!"
"It's a duck!"
"If you think that's a rabbit, then you need to have your eyes check because ..." the student never completed his sentence as the teacher punched the board with maximum force. The whole class went silent.
"Okay, let's stop here for now. It's obvious that you guys are over-excited about it. Have you ever considered that you are wrong?"
The student fell silent. "But it's clearly a picture of a duck."
"Well, now, it's clear that YOU have a picture of a duck. Considering that each and every single one of you have your own picture, don't you think that maybe the other person have a picture of a rabbit?"
This has not crossed the mind of the student. He bowed his head in shame.
"There, you see? It's just a simple mistake. A simple misunderstanding. Clearly, some of you have the picture of a duck, and others have a picture of a rabbit. Why do you think I sorted out the class in two, eh?" The teacher was smug. It now becomes clear that the teacher is setting up the class for failure yet again. The students all assume that each student have the same picture. It turns out that there are two different pictures. Worse, they have accused the other side of being a liar, even though they were telling the truth. The teacher has warned them of this, yet they fell into it.
"Okay, so back to your original seat, and let me tell you: I should be spanking each and every one of you! You, who are so ignorant and readily accuse of the other students of being a liar when in fact, they are telling you the truth! Now, tell me, why should I spare you from the most extreme beatings?"
The guilty students are all so embarassed. Then, Peter, who was smiling all this time, asked, "May we see the picture?"
A smile was upon the teacher. "I see we have someone who is wise. In fact, here is the picture!" The teacher put up a large version of the picture on the board for all to see. A knock on the classroom door. "Enter." Says the teacher.
Another teacher was on the door. "What was that bang on the wall?" She asked. She was the biology teacher, teaching on the other side of the wall.”
"Oh, that was me hitting the board." Said the teacher calmly.
"Why would you do that?"
"Oh, there was an all-out war going on, and I decide to stop it before it got too far, right?" The teacher was looking at the guilty students when he says this. The students all bowed their head in embarassment.
"Well, try to control your class better. The whole classroom was scared because of it!"
"I think I did fine. No holes on the wall, after all. Gya ha ha ha!" The other teacher did not think that's funny, but she left without fuss.
"All right, so what do you think?" The teacher asked the class.
"We're sorry. It won't happen again."
"Damn right, it won't! Next time it happens again, I'll go directly to hard beatings!"
The student coiled in fear.
"But that's not the question. What do you think of the picture?"
"Well, the picture is upside-down, but it's clearly a picture of a rabbit." "Duck" said another student.
The whole class fell silent. The teacher laughed and laughed.
"Gya ha ha ha! Can't you tell whether you're looking at a rabbit or a duck?" The students all fell silent.
"Okay, here's the thing. Remember the half-full,half-empty glass lesson yesterday?"
"Yes, teacher."
"What did that tell you?"
"That some situations have different interpretations."
"Yes, and...?"
"And that we shouldn't blame the other side for having a different interpretation."
"Correct. Now why did you blame the other side for having seen a different animal other than you?"
"Because, well, because we don't see the other animal!"
The teacher laughed. "This here is actually a very famous picture. You've seen this picture before, haven't you?" He was talking to Peter."
"Yes, teacher. It's one of those ambiguous picture that can be seen as a duck or a rabbit, depending on how you orient the picture."
All the other students were in shock! They were all stunned!
"See," the teacher re-oriented the picture on the wall one way. "Here is the head of the rabbit, and here is the ears. See that?"
"Oooohhhh," all the students who saw the duck now realized their errors.
"Now, check this out." The teacher re-oriented the picture again. "See, this is the head of the duck, and this is the bill."
"Ooooohhh," all the students who saw the rabbit now laughed nervously.
"And despite repeated warnings that you will err, and accuse the other side of being wrong when they're not. You did it, anyway. So, tell me. Is all your promises of being good and won't do it mean anything at all?"
The students were all embarrassed that they fell to the trap so easily. "But teacher, we didn't know that there was another animal in the picture."
"Correct. But remember what I said before: If you do not see any reason why the other side is correct, the least you can do is ask for justification before attacking and punishing the other side! You are being ignorant and yet, claimed superiority of intellect! What's wrong with you?"
"We're sorry, teacher. We didn't mean to."
"And that is the hardest lesson of all. Most sufferings in the world is not caused by evil minds, determined to destroy the world." The student listened intently to the words, instinctively knowing that wisdom is being doled out in the mist of harsh words. "In fact, most suffering is caused by mere ignorance. Unwillingness to acknowledge self wrong and the possibility of the other side being right. Therefore, it is of the utmost importance that unless you can find something that is definitely wrong with the other person, you cannot blame their position at all!"
The students cannot believe it, yet, if the simple exercise being shown here is indicative of the bigger picture, it must be true! The implication is staggering and all the students are silent, not knowing what to expect.
"Okay, class, let's move on." Said the teacher after a while. "This time, we're all going to describe one picture. I'll put the picture on the board here for all to see. And just so that there's no confusion, I'm going to tell you right now that this is a picture of a woman. Not a duck. Not a rabbit. A woman. Got it?"
The teacher then took off the picture of animal, and put up a picture of a woman. Peter almost couldn't help himself, trying to stiffle his laughter. The teacher smiled a knowing smile.
The rest of the class, though, suspicious, couldn't tell what's going on. They simply know, instinctively, that bad things are about to happen yet again.

“What are you waiting for? Get cracking! Start describing the picture! Get out a piece of paper and write down the descriptions! 5 minutes!” The teacher barked his orders.

All the students hurriedly pulled out a fresh piece of paper and furiously write down the description of the picture.
"Time's up! Get your papers here.” The teacher scanned the papers as he collected them. “Gya ha ha ha! Only one passing grade? I'm so disappointed in you!" The teacher was laughing with glee. He certainly didn't look disappointed at all.
"What's wrong? It's a picture of a woman, right? I think we do a good job in describing it!" Said a student.
"Is that right? Is that a young woman or an old one?"
"Young."
"Old."
All the students looked upon one another, suddenly realizing the situation. It's another ambiguous picture! They looked helplessly at the teacher for hints.
"Is the woman looking this way or that way?" Just like that, the vision becomes clear. The picture of a pretty young woman was looking away. She was wearing necklace. Yet, when seen as a woman looking at the viewer, the necklace becames ugly teeth, the chin becomes ugly nose, and the ugly woman was old, indeed!
All the students felt miserable. Clearly, they have failed in their assignment yet again. "Only one passing grade?"

The students were wondering who might that be? Who among them was able to see through the ambiguous picture?
"Peter did it. Of course, he's seen these picture before. Didn't I say they're famous pictures?" Yes, he did. None of the other students have ever seen it, though. "Still, you should've figured it out by now. Haven't I been stressing multiple solutions these past few days? Once you find a good answer, find a better one!"
There was nothing the student can do. They all looked sadly at the papers stacked on the teacher's desk. The teacher noticed it.
"Normally, I'd say curved grade, but since this is one 100, with the rest zeros. There's no helping it! Gya ha ha ha!"
The students all feel miserable. Complete failures! What an embarassment to the school, and family! Cannot do such a simple thing as to see alternative solution!

“So, what have we learned so far?” asked the teacher.

“We were so wrong in our thinking of the picture.”

“And...?”

“And we blamed the other side without asking for clarification.”

“And that's bad because...?”
“Because that cause the other side to get angry and defensive, and we argued needlessly.”

“And the rule that you violated is...?”

“We needed to ask the other person why they think the picture is a rabbit or a duck. We needed to get to the other's point of view, and we didn't.”

“That's right. It's a hard earned lesson, and unfortunately, one that you will have to learn over and over again. There are various forms that this may take. Today, it's ambiguous picture, and truthfully, this is so easy to be understood. However, not everything is so easily understood.

“Take opinions, for example. Let's say you want to order a large meal. Unless there is a clear size differentiation between small, medium, and large, you absolutely cannot say a 'large' meal. You need to be specific. You may say a '2000 calorie' meal. Or you can say 'quarter pound' burger. However, everybody has a different notion of 'large'. Who is to say that large is 1 cup of rice, or 2, or 3, or 10? You have to be specific in saying things, do you understand?”

“Yes, teacher.”

“Furthermore, you have to take care in using the right measurement. You cannot say that large is 10 dollars. Or 100 dollars. Dollar is not a measurement of size. Caviar can be 100 dollars and small size.”

“Finally, there are things that are absolutely blameless. Taste and preferences, for example. I like hot food, you like salty food. I like blue and you like red. Neither of us is wrong. To say otherwise, is to be inciting war!”

4.3 NOT, AND, OR, XOR + parenthesis
"Well, the way I see it, you guys are so hopeless that maybe we should ease of the level of difficulty a bit. Let's start with binary. Ones and zeros."
"You understand TRUE and FALSE, right? So, let's expand that knowledge a bit. We're going to use numbers. So, we're going to interpret that 0 is FALSE, and 1 is TRUE.
"Now, we're going to take several of this numbers and join them together. Let's go through all the operators. NOT, AND OR, and XOR. Now, repeat after me.
If something is NOT TRUE, then it is FALSE.
If something is NOT FALSE, then it is TRUE.

Next, the AND operator.
If something is TRUE and TRUE, then it is TRUE.
If something it TRUE and FALSE, then it is FALSE.

If something is FALSE and FALSE, then it is false.

Here is the 'truth' table about AND

AND 0 1
0 0 0
1 0 1

Now here is the truth table of OR
OR 0 1
0 0 1
1 1 1

And here is the truth table for XOR
XOR 0 1
0 0 1
1 1 0

"Got it? Good. Now let's practice on some binary numbers. For those of you with computers already, you can practice on your computer. For now, let's do it by hand.

“What do you get when you do 1 AND 1?” asked the teacher.

“We get 1!” said the students.

“Correct. Now how about 1 OR 1?”

“We still get 1!” said the students.

“Correct. Now do 1 XOR 1.”

“We still get 1!” said the students.

“Good. That's easy, right?” asked the teacher. The students all nodded their heads. “You need to memorize these values. Now, either you sit down and memorize them silly, or you can do lots of practice and hope that it will be absorbed automatically. Let's do the latter, because you can certainly do the former at home!”

The teacher then wrote a series of numbers on the board.

0000 0 1000 8

0001 1 1001 9

0010 2 1010 A

0011 3 1011 B

0100 4 1100 C

0101 5 1101 D

0110 6 1110 E

0111 7 1111 F

“Alright. What we have there is the hexadecimal numbering system. That is, instead of a 10 digit decimal system, we have a 16 digit hexadecimal system. This is used a lot by binary system because it's a very convenient way to write 4 bits together. Now, what I want you to know is that there are 4 bits to a hex, and you need to memorize this as well.

“What we're going to do is we'll be doing the operator on the hexadecimal numbers. That is, we're going to do the operation on four bits at once.”

“Now, what we're doing is exactly like adding numbers. The difference is, instead of using add operator, we're using AND, OR, and XOR operator. Like this:

0110 + 0011 = 1001 (6+3=9)

0110 AND 0011 = 0010 (6&3=2)

0110 OR 0011 = 0111 (6|3=8)

0110 XOR 0011 = 0101 (6xor3=5)

“Does every body got that? Of course, when it comes to your homework, all the questions and answers will be in hexadecimal form! Notice that AND has the symbol '&', OR has the symbol '|' and XOR has no definite symbol, so it gets written out.

“Now, here's something interesting. Suppose you want to increment a value. Let's say you want to increment 5 to 6. Since increment always add by one, how would you do it via Boolean operators. That is NOT, ADD, OR, and XOR?”

The students all look at each other. “Can we do really do that? Why not just use ADD by one?”

“The reason is because adding is actually a rather expensive operation compared to increment. By the way, you can shift left and right as well. Now there are two kinds of shift. The first one is shift by zero. That is, when you shift left or right, the new bits will all be zeros. Another kind of shift is rotate. That is the far side bit will go across to the other side. Here are some examples:

0001 << 2 = 0100 (1<<2=4)

0110 >> 2 = 0001 (6>>2=1)

“You may notice that each shift is like multiplying or dividing by 2. Just like the decimal system where each shift is like multiplying or dividing by ten. Binary systems is so simple, that you should have no trouble doing it. So, lets increment 5 to 6. If you think about it, that's simply the NOT operator bit by bit until the first zero. Isn't binary so simple?”

0000 → 0001

0001 → 0000 → 0010

0010 → 0011

0011 → 0010 → 0000 → 0100

0100 → 0101

0101 → 0100 → 0110

0110 → 0111

0111 → 0110 → 0100 → 0000 → 1000

“And so on. Here's another way to look at it. Fill the bits with 1s until first zero. Then XOR that with the original number:

0000 xor 0001 = 0001

0001 xor 0011 = 0010

0010 xor 0001 = 0011

0011 xor 0111 = 0100

0100 xor 0001 = 0101

0101 xor 0011 = 0110

0110 xor 0001 = 0111

0111 xor 1111 = 1000

“So, which one is better? It depends. If you're wiring the hardware, then the NOT method is better. However, when you're dealing with computer program instruction that operates on bytes, then the XOR method is better. All we have to do is to come up with the masking bit.

“In truth, coming up with the masking bit using byte size operation isn't too easy, but I'm sure that if you try hard enough, you will be able to do it! There are several steps that you need to do in order to maintain states between passes. That's not too simple and easily done with byte operations.

“If you have access to bit(n) command, which lets you do bit manipulation, or if you can do comparison operations, not to mention loop, then it'll be trivial. If you have access to the Internet, you will see that all the existing explanations will use these commands. That's because, frankly, doing it using byte operation is a great big pain. Gya ha ha ha!”

The students all don't know what to say. Does that mean the teacher has done it the hard way? Is that a good thing? (For answer, see Appendix A)

“Here's something to ponder. Do you see the bits that goes 0 to 15? Now, how do you suppose you'll be representing negative numbers? Does anyone have any idea?”

The students thought about it for a while. Finally somebody said, “Shouldn't there be a sign bit somewhere?”

“Correct. In fact, the most significant bit (MSB) is used to signify the sign bit. So, start putting in those negative numbers. Recast those numbers with high bit set to negative numbers!”

The students all got busy with their papers. After a while, they came up with this:

0000 0 1000 -0

0001 1 1001 -1

0010 2 1010 -2

0011 3 1011 -3

0100 4 1100 -4

0101 5 1101 -5

0110 6 1110 -6

0111 7 1111 -7

“Alright, let's see! Ha! I thought so. You're treating the MSB as the sign, literally! I see that there are two zeros, there. So, tell me, do you know alternative way to do this?”

The students all think about it for a while. “But teacher, this is the most natural way to do it! Why would we want to do it another way?”

“Think about it,” the teacher explained, “What happens when you increment the numbers? How about when you increment number 7?”

“Then the number will go to -0! Uh, is that bad?”

“Sure is. When you want to increment the numbers, you don't want to have the numbers to go backwards just because it's in the negative zone! So, why don't you try it again?”

The students tried once more. This is what they came up with:

0000 0 1000 -8

0001 1 1001 -7

0010 2 1010 -6

0011 3 1011 -5

0100 4 1100 -4

0101 5 1101 -3

0110 6 1110 -2

0111 7 1111 -1

“Aha! Now you have discovered the binary number representation that is called 'twos complement'! What do you think?”

“I'm having trouble accepting that 1111 means -1.” said a student.

“Gya ha ha ha! Looks weird, doesn't it? It took me a full 8 weeks before I come to terms with it! So, don't worry about it. Actually, this kind of information isn't strictly necessary for beginners. However, one of these days, you will come to terms with it, so, why not learn it now?

“In any case, would you be willing to try to come up with the ways to turn a positive number to negative numbers and vice-versa?”

The students all moaned, and started to concentrate on the task. It was not an easy task for the students. After all, they've only just learned negative number representation recently.

The bell rang. Class time is over! The teacher gathered the papers. “I don't see too many correct answers here. And it's all your fault, I may add.”

“But teacher, it's not easy to do!”

“I know that, but the very least you can do is try to re-arrange the numbers like this:”

0000 0

0001 1 1111 -1

0010 2 1110 -2

0011 3 1101 -3

0100 4 1100 -4

0101 5 1011 -5

0110 6 1010 -6

0111 7 1001 -7

1000 -8

“See how it lines up nicely? Then you'll have an easier time to do it. Not that it's easy! At least make it as easy as possible! No need to be a superhero when you can do it the easy way! Gya ha ha ha!”

The students bowed their head in embarassment. They simply hadn't thought of re-casting the problem to make it easy.

“Tell you what,” the teacher said. “Why don't I make it a homework. Remember, from positive to negative and from negative to positive. Once you have one, you should have the other. Okay?”

“Yes, teacher.”

“Those of you who managed to get close today will get extra points! Oh, by the way, start thinking about adding two numbers. We'll be doing that tomorrow! Wouldn't want to look stupid like you did today, right? Gya ha ha ha!”

The students are all shaken up. Computer programming is indeed a very hard subject!

The next day, half the students managed to turn in the correct answer to the problem. Turns out it's very simple. To switch sign of number N: Increment (NOT N). That is, you take the bits of the number and apply the NOT operator, then you increment it by one. That's it! That is the convenience factor of twos complement representation.

“So, now, ready to add two numbers? You all know how to add two decimal numbers, right? So how do you add two binary numbers using the boolean operators?”

No answer was fortcoming. No one managed to get the answer.

“Ha, one would think that once you've learned to add two numbers using decimal system, you'll have an easy time doing it binary! Here goes, adding number A to B with Carry C:

A=number 1

B=number 2

C=(A and B)<<1. Remember, multipy by 2!

B=A xor B

A=C

Repeat from step C onward until done.

Peter raised his hand. “Yes?” asked the teacher.

“Teacher, I was really close to the solution, but I didn't think I can use the shift operator.”

“Oh, really? Well, how would I know that? Did you write the solution using shift operator down?” Peter shook his head. “It's too late this time. Next time, write it down, so I'll know. Even if you don't get it, at least you'll get credit for trying.”

4.4 The world as black and white

“So, in fact, I could have gotten some credit after all.” Peter was at the teacher's office during consulting hours per usual.

“Don't get your hopes up. If you cannot handle such an easy assignment, your chances of high score wouldn't be too good, anyway. But yes, you will get some credits for trying.”

“And you're okay with that? Even if I get the answer wrong?”

“Hmmm, of course, the most important thing is to get the right answer. However, a wrong path explained will tell me how to shape my instructions so you don't go down the wrong path in the first place. Think of it this way. If every time I say 'North', you go South, then pretty soon, I'll be saying 'South', just to see if you'll go North. Understand?”

“Ah, I see. So, you're basically taking feedback from the students so you can adjust your teaching materials.”

“Sure. After all, this is a school. I need to be giving you the materials in such a way that most students will understand. Basically, try to get the most outcome from the students.”

“Has it been working so far?”

“Unfortunately not. I keep adjusting my expectation downward. You guys really are stupid, you know? It's like, the answer is obvious, right in front of you, and yet you still can't see it!”

“Not everybody has computer programming experience.”

“Well, we're not into computer programming, yet. So far, all we've done is some pattern recognition. Take the flipping of the numeric sign, for example. I think it is obvious that if you want to recognize a pattern from positive/negative numbers, you lined them up together. You don't even do that! Why is that?”

“I guess, we've never been taught to do so.”

“Obviously. But here's the thing: There are so many different solutions available, and you guys just pick the first one that comes to mind. Obviously, that's not a good solution. So what you need to do is to step back, and try a completely different solution. Yet, none of you do that! That's not computer programming. That's basic problem solving! I find it hard to believe that you guys are in high school!”

“So, we need to try different approaches to a problem?”

“Correct. In fact, I have a saying: 'Don't do one thing many times. Do many things, once!' Which basically means that you need to survey all possible solutions and pick the most promising ones, yet be able to discard attempted solution if it doesn't work.”

“Ah, look before you leap.”

“Exactly. It is the definition of insanity to expect a different result from the same attempt.”

“So, are we going to stay with binary programming for a long time?”

“Probably not. We're going to wrap things up nicely, then have a good solid exam. Looking at the world from binary perspective can be a pain, sometimes.”

“What do you mean?”

“Most people think that there are two answers to a yes or no question: Yes, or No.”

“That would be my assumption, yes.”

“And yet, there are actually 4 different applicable answers.”

“Really? What are they?”

“Yes, No, Maybe, and Don't Know.”

“Hmmmm. I see. Just because it's a simple question, doesn't mean the person knows the answer.”

“And that's what we'll be doing next. Gya ha ha ha!”