All posts by djmordigal

When I was in college at RIT, I was in the IT program. The curriculum exposed me to many high-level programming languages and technologies, but it was only after I started my career at IBM that I did anything lower-level than Java.

Among the things I learned there was IBM Assembler, the assembly language for mainframes (now called Z Systems). It’s the lowest level you can reach without writing machine code by hand. Although it’s not used very much in mainstream application development anymore, it still comes with the operating system and many applications are at least partially written in it, including some clients’ own programs.

One of the neatest low-level things I learned was how the processor is dealing with bit (boolean-like) values.

The Logical Operations

Most of us are familiar with the logical operations AND, OR, and Exclusive OR (XOR), but a quick overview doesn’t hurt. Given two bits, p and q:

p	q	p & q
0	0	0
0	1	0
1	0	0
1	1	1

p	q	p | q
0	0	0
0	1	1
1	0	1
1	1	1

p	q	p ^ q
0	0	0
0	1	1
1	0	1
1	1	0

Using a Bit Mask

Most of us also know the relationship between bits and bytes: a bit (short for “binary digit”) is a single number with two possible values: 0 and 1. A byte is a group of 8 consecutive bits.

Since the behavior is not obvious, most of us don’t think about the fact that when you declare a boolean-like variable in a high-level language, you really get the full byte. This is because in computer memory, only bytes are addressable, not individual bits. Therefore, it is simplest (and really only possible) for the processor to work with the whole byte at a time. Effectively, what happens is that one bit is selected to hold the actual value, and the remaining 7 bits are not used.

For the purposes of these examples, let’s pretend that the first (leftmost) bit is used to hold the actual value of the boolean variable. Therefore, a “true” value would be represented by 10000000, and a “false” value would be represented by 00000000.

To manipulate individual bits within a single byte, we use a bit mask. A mask is itself just another byte, but it serves a special purpose: to instruct the processor which bits are to be operated upon.

Using the truth tables above, we can draw the following conclusions about the logical operations.

For AND:

• ANDing a bit with 0 will always set it to 0, no matter its original value. This is because both bits of an AND operation must be 1 in order for the result to be 1, so using a 0 in the mask will guarantee that at least one of the bits is 0.
• ANDing a bit with 1 will always leave it unchanged.

For OR:

• ORing a bit with 0 will always leave it unchanged.
• ORing a bit with 1 will always set it to 1, no matter its original value. This is because only one bit of an OR operation needs to be 1 in order for the result to be 1, so using a 1 in the mask will guarantee that at least one of the bits is 1.

For XOR:

• XORing a bit with 0 will always leave it unchanged.
• XORing a bit with 1 will always flip (negate) it–that is, 0 becomes 1 and 1 becomes 0.

The examples below will illustrate these concepts in more detail. The examples are not specific to any particular programming language, but I’ll use Java-like syntax since most programmers are familiar with it.

Setting a Boolean Variable to “true”

Let’s pretend we declare a boolean variable called myBool:

boolean myBool;

In most languages, the default value of myBool would be false. In memory, the byte allocated to hold the variable myBool would simply look like this: 00000000.

If we set this variable to true:

myBool = true;

Internally, the operation would look like this:

  00000000    <-- current value of myBool
| 10000000    <-- ORed with a bit mask
  --------
  10000000    <-- final result

We essentially pair the corresponding bits in each byte (the variable myBool and the bit mask) to perform the operation. The first bit of myBool is 0, and the first bit of the mask is 1. Since one of these bits is 1, the result of the OR for the first bit position is 1. And since the bits in the remaining 7 positions of each byte are all 0, the result of the rest of the OR operation (for these 7 bits) is also 0. Effectively, ORing these 7 bits with 0 also leaves them unchanged.

Setting a Boolean Variable to “false”

The inverse applies for setting a boolean variable to false. The high-level language statement:

myBool = false;

Results in an AND operation:

  10000000    <-- current value of myBool (after setting it to true above)
& 01111111    <-- ANDed with a bit mask
  --------
  00000000    <-- final result

The operation is performed the same way, pairing each corresponding bit in the two bytes. The first bit of myBool is now 1 (after setting it to true above), and the first bit of the mask is 0. Since only one of these bits is 1, the result is 0.

Notice that in the mask, the remaining 7 bits are all 1. This is because, as in the previous example, we want to leave the remaining 7 bits of myBool unchanged.

Negating (Flipping) a Boolean Variable

Another common programming practice is to negate the value of a boolean variable; that is, a value of true becomes false and a value of false becomes true. The high-level language statement:

myBool = !myBool;

Results in an XOR operation:

  00000000    <-- current value of myBool (after setting it to false above)
^ 10000000    <-- XORed with a bit mask
  --------
  10000000    <-- final result

Repeating the same high-level language statement again results in the same operation, but with the opposite effect:

  10000000    <-- current value of myBool (after flipping it to true above)
^ 10000000    <-- XORed with a bit mask
  --------
  00000000    <-- final result

Again, the remaining 7 bits of the mask are all 0, because we want to leave the remaining 7 bits of myBool unchanged.

Testing a Bit

Recall from the conclusions under the above truth tables that in order to leave a bit unchanged, we can AND that bit with 1.

This means that this operation will yield a result which is equal to the original bit. Why then, you might ask, is this useful?

It turns out that these bitwise operations, as part of their processing, set another special value internal to the CPU called the condition code. The terminology for the condition code varies by processor architecture, but it serves the same general purpose: to indicate the result of an instruction that sets it. Not all instructions change (or set) the condition code.

After the bitwise instruction is performed and the condition code set to indicate the result, a subsequent instruction in the program tests the condition code. This test instruction causes a “branch” (or “jump”) to another instruction in the program, if the condition code’s value matches that specified by the test instruction–altering the program’s flow of execution. Otherwise, the program simply moves forward (“falls through”) to the next instruction. This is the basic behavior of if statements in a high-level language.

Suppose we have the following high-level language statements:

if(myBool) {
    // do something if myBool is true
} else {
    // do something if myBool is false
}

We can test the value of myBool (which, remember, is represented by the leftmost bit in a byte) by ANDing its bit with 1:

  10000000    <-- current value of myBool ("true")
& 10000000    <-- AND with mask, "selecting" the first bit
  --------
  10000000    <-- result

Since the result indicates that the selected bit is indeed 1, the AND instruction would then set the CPU’s condition code to indicate as such. Generally speaking, this condition code value would probably be a number that semantically means “result was not zero”.

A subsequent instruction would then test the condition code. If the test instruction tells the CPU to branch to another instruction, X, on a “not zero” condition, the branch to instruction X would occur, thus altering the program’s flow. If the test instruction tells the CPU to branch to instruction X on a “zero” condition, the branch would not occur, and the program would simply fall through to the next instruction.

The opposite, of course, would occur if myBool was set to false:

  00000000    <-- current value of myBool ("false")
& 10000000    <-- AND with mask, "selecting" the first bit
  --------
  00000000    <-- result

The CPU’s condition code would be set to a number indicating “result was zero” (this condition code number is likely 0 itself). Again, a subsequent instruction would test the condition code; if the test instruction tells the CPU to branch on a “zero” condition, the branch occurs. If the test instruction tells the CPU to branch on a “not zero” condition, the branch does not occur, and program execution simply falls through to the next instruction.

Using AND to Test for an Odd or Even Number

At some point in your programming career, you were no doubt tasked with determining whether an integer was even or odd. We all know what makes an even number, even: it’s divisible by 2. More specifically: when the number is divided by 2, the remainder is 0.

In a high-level language, like Java or C, the modulo operator (usually a percent sign: %) is used to determine this. The modulo operator does the division problem, but it returns the remainder instead of the quotient.

int myInt;

// determine value of myInt ...

if(myInt % 2 == 0) {
    // do something if myInt is even
} else {
    // do something if myInt is odd
}

At this point, it’s worth noting that most compilers for high-level languages have a feature called optimization, which means that the compiler attempts to generate the most efficient executable code for accomplishing the task. A good example of this is for if statements for which the condition is, at compile time, always known to be true (e.g., comparing one constant value to another constant value). In this case, an optimizing compiler would not generate executable code to check the if statement condition; it would simply generate the code that corresponds to the if statement, which will always run.

For determining whether an integer is even or odd, a non-optimizing compiler would likely see the modulo expression and generate the executable code something like this:

• Set up the operands for a division instruction (the current value of myInt and the number 2–these values would be placed in CPU registers or simply referenced by their locations in memory).
• Perform the division instruction, saving the quotient in one register and the remainder in another.
• Test the value in the register containing the remainder and set the condition code accordingly.
• Test the condition code to determine whether a branch to another instruction should occur.

Although all of these steps would execute in a tiny fraction of a second, it is still relatively inefficient and cumbersome. How can we do this better?

In binary, this is very easy. Since binary is base 2, all numbers that are multiples of 2, and 0 itself, end with a 0 (much like how in our base 10 (decimal) system, all multiples of 10 end with 0). All odd numbers end with a 1. To illustrate, have a look at the numbers 0-9 in binary:

Binary	Decimal
0000	0
0001	1
0010	2
0011	3
0100	4
0101	5
0110	6
0111	7
1000	8
1001	9

Notice how the last (rightmost) digit alternates between 0 and 1 for even and odd numbers. Therefore, all we really have to do is test the last bit.

Let’s pretend the variable myInt is an 8-bit number and has a value of 12 (randomly chosen). The bitwise AND for the test would look like this:

  00001100  <-- binary representation of 12
& 00000001  <-- AND with mask, "selecting" the last bit
  --------
  00000000  <-- final result = 0, number is even

The result of the AND operation is 0, indicating that the value of myInt is indeed even.

Let’s do the same for an odd number, 73:

  01001001  <-- binary representation of 73
& 00000001  <-- AND with mask, "selecting" the last bit
  --------
  00000001  <-- final result = 1, number is odd

In both cases, the AND instruction would set the condition code of the CPU to indicate the result. Therefore, all that really has to be done afterward is to check the condition code for a “zero” or “not zero” condition; no division and further testing required.

Pretty neat, eh?