Truth, Falsehood, and Binary Numbers | Programming from the Ground Up

Now we've seen that the computer stores everything as sequences of 1's and 0's. Let's look at some other uses of this. What if, instead of looking at a sequence of bits as a number, we instead looked at it as a set of switches. For example, let's say there are four switches that control lighting in the house. We have a switch for outside lights, a switch for the hallway lights, a switch for the living room lights, and a switch for the bedroom lights. We could make a little table showing which of these were on and off, like so:

 Outside   Hallway   Living Room   Bedroom   On        Off         On          On

It's obvious from looking at this that all of the lights are on except the hallway ones. Now, instead of using the words "On" and "Off", let's use the numbers 1 and 0. 1 will represent on, and 0 will represent off. So, we could represent the same information as

 Outside   Hallway   Living Room   Bedroom    1         0            1          1

Now, instead of having labels on the light switches, let's say we just memorized which position went with which switch. Then, the same information could be represented as

 1            0            1          1

or as

This is just one of many ways you can use the computers storage locations to represent more than just numbers. The computers memory just sees numbers, but programmers can use these numbers to represent anything their imaginations can come up with. They just sometimes have to be creative when figuring out the best representation.

Not only can you do regular arithmetic with binary numbers, they also have a few operations of their own, called binary or logical operations . The standard binary operations are

Before we look at examples, I'll describe them for you. AND takes two bits and returns one bit. AND will return a 1 only if both bits are 1, and a 0 otherwise. For example, 1 AND 1 is 1, but 1 AND 0 is 0, 0 AND 1 is 0, and 0 AND 0 is 0.

OR takes two bits and returns one bit. It will return 1 if either of the original bits is 1. For example, 1 OR 1 is 1, 1 OR 0 is one, 0 OR 1 is 1, but 0 OR 0 is 0.

NOT only takes one bit and returns its opposite. NOT 1 is 0 and NOT 0 is 1.

Finally, XOR is like OR, except it returns 0 if both bits are 1.

Computers can do these operations on whole registers at a time. For example, if a register has 10100010101010010101101100101010 and another one has 10001000010101010101010101111010, you can run any of these operations on the whole registers. For example, if we were to AND them, the computer will run from the first bit to the 32nd and run the AND operation on that bit in both registers. In this case:

 10100010101010010101101100101010 AND 10001000010101010101010101111010 -------------------------------- 10000000000000010101000100101010

You'll see that the resulting set of bits only has a one where both numbers had a one, and in every other position it has a zero. Let's look at what an OR looks like:

 10100010101010010101101100101010 OR 10001000010101010101010101111010 -------------------------------- 10101010111111010101111101111010

In this case, the resulting number has a 1 where either number has a 1 in the given position. Let's look at the NOT operation:

 NOT 10100010101010010101101100101010 ------------------------------------     01011101010101101010010011010101

This just reverses each digit. Finally, we have XOR, which is like an OR, except if both digits are 1, it returns 0.

 10100010101010010101101100101010 XOR 10001000010101010101010101111010 -------------------------------- 00101010111111000000111001010000

This is the same two numbers used in the OR operation, so you can compare how they work. Also, if you XOR a number with itself, you will always get 0, like this:

 10100010101010010101101100101010 XOR 10100010101010010101101100101010 -------------------------------- 00000000000000000000000000000000

These operations are useful for two reasons:

The computer can do them extremely fast
You can use them to compare many truth values at the same time

You may not have known that different instructions execute at different speeds. It's true, they do. And these operations are the fastest on most processors. For example, you saw that XORing a number with itself produces 0. Well, the XOR operation is faster than the loading operation, so many programmers use it to load a register with zero. For example, the code

  movl  $0, %eax

is often replaced by

  xorl  %eax, %eax

We'll discuss speed more in Chapter 12, but I want you to see how programmers often do tricky things, especially with these binary operators, to make things fast. Now let's look at how we can use these operators to manipulate true/false values. Earlier we discussed how binary numbers can be used to represent any number of things. Let's use binary numbers to represent what things my Dad and I like. First, let's look at the things I like:

 Food: yes Heavy Metal Music: yes Wearing Dressy Clothes: no Football: yes

Now, let's look at what my Dad likes:

 Food: yes Heavy Metal Music: no Wearing Dressy Clothes: yes Football: yes

Now, let's use a 1 to say yes we like something, and a 0 to say no we don't. Now we have:

 Me Food: 1 Heavy Metal Music: 1 Wearing Dressy Clothes: 0 Football: 1 Dad Food: 1 Heavy Metal Music: 0 Wearing Dressy Clothes: 1 Football: 1

Now, if we just memorize which position each of these are in, we have

 Me 1101 Dad 1011

Now, let's see we want to get a list of things both my Dad and I like. You would use the AND operation. So

 1101 AND 1011 -------- 1001

Which translates to

 Things we both like Food: yes Heavy Metal Music: no Wearing Dressy Clothes: no Football: yes

Remember, the computer has no idea what the ones and zeroes represent. That's your job and your program's job. If you wrote a program around this representation your program would at some point examine each bit and have code to tell the user what it's for (if you asked a computer what two people agreed on and it answered 1001, it wouldn't be very useful). Anyway, let's say we want to know the things that we disagree on. For that we would use XOR, because it will return 1 only if one or the other is 1, but not both. So

 1101 XOR 1011 -------- 0110

And I'll let you translate that back out.

The previous operations: AND, OR, NOT, and XOR are called boolean operators because they were first studied by George Boole. So, if someone mentiones boolean operators or boolean algebra, you now know what they are talking about.

In addition to the boolean operations, there are also two binary operators that aren't boolean, shift and rotate. Shifts and rotates each do what their name implies, and can do so to the right or the left. A left shift moves each digit of a binary number one space to the left, puts a zero in the ones spot, and chops off the furthest digit to the left. A left rotate does the same thing, but takes the furthest digit to the left and puts it in the ones spot. For example,

 Shift left  10010111 = 00101110 Rotate left 10010111 = 00101111

Notice that if you rotate a number for every digit it has (i.e. - rotating a 32-bit number 32 times), you wind up with the same number you started with. However, if you shift a number for every digit you have, you wind up with 0. So, what are these shifts useful for? Well, if you have binary numbers representing things, you use shifts to peek at each individual value. Let's say, for instance, that we had my Dad's likes stored in a register (32 bits). It would look like this:

 00000000000000000000000000001011

Now, as we said previously, this doesn't work as program output. So, in order to do output, we would need to do shifting and masking. Masking is the process of eliminating everything you don't want. In this case, for every value we are looking for, we will shift the number so that value is in the ones place, and then mask that digit so that it is all we see. Masking is accomplished by doing an AND with a number that has the bits we are interested in set to 1. For example, let's say we wanted to print out whether my Dad likes dressy clothes or not. That data is the second value from the right. So, we have to shift the number right 1 digit so it looks like this:

 00000000000000000000000000000101

and then, we just want to look at that digit, so we mask it by ANDing it with 00000000000000000000000000000001.

 00000000000000000000000000000101 AND 00000000000000000000000000000001 ----------------------------------- 00000000000000000000000000000001

This will make the value of the register 1 if my Dad likes dressy clothes, and 0 if he doesn't. Then we can do a comparison to 1 and print the results. The code would look like this:

  #NOTE - assume that the register %ebx holds  #       my Dad's preferences  movl  %ebx, %eax #This copies the information into %eax so                   #we don't lose the original data  shrl  $1, %eax   #This is the shift operator.  It stands                   #for Shift Right Long.  This first number                   #is the number of positions to shift,                   #and the second is the register to shift  #This does the masking  andl  $0b00000000000000000000000000000001, %eax  #Check to see if the result is 1 or 0  cmpl  $0b00000000000000000000000000000001, %eax  je    yes_he_likes_dressy_clothes  jmp   no_he_doesnt_like_dressy_clothes

And then we would have two labels which printed something about whether or not he likes dressy clothes and then exits. The 0b notation means that what follows is a binary number. In this case it wasn't needed, because 1 is the same in any numbering system, but I put it there for clarity. We also didn't need the 31 zeroes, but I put them in to make a point that the number you are using is 32 bits.

When a number represents a set of options for a function or system call, the individual true/false elements are called flags. Many system calls have numerous options that are all set in the same register using a mechanism like we've described. The open system call, for example, has as its second parameter a list of flags to tell the operating system how to open the file. Some of the flags include:

O_WRONLY

This flag is 0b00000000000000000000000000000001 in binary, or 01 in octal (or any number system for that matter). This says to open the file in write-only mode.

O_RDWR

This flag is 0b00000000000000000000000000000010 in binary, or 02 in octal. This says to open the file for both reading and writing.

O_CREAT

This flag is 0b00000000000000000000000001000000 in binary, or 0100 in octal. It means to create the file if it doesn't already exist.

O_TRUNC

This flag is 0b00000000000000000000001000000000 in binary, or 01000 in octal. It means to erase the contents of the file if the file already exists.

O_APPEND

This flag is 0b00000000000000000000010000000000 in binary, or 02000 in octal. It means to start writing at the end of the file rather than at the beginning.

To use these flags, you simply OR them together in the combination that you want. For example, to open a file in write-only mode, and have it create the file if it doesn't exist, I would use O_WRONLY (01) and O_CREAT (0100). OR'd together, I would have 0101.

Note that if you don't set either O_WRONLY or O_RDWR, then the file is automatically opened in read-only mode (O_RDONLY, except that it isn't really a flag since it's zero).

Many functions and system calls use flags for options, as it allows a single word to hold up to 32 possible options if each option is represented by a single bit.