3.7 Logical Operations on Bits
There are four main logical operations we'll need to perform on hexadecimal and binary numbers: AND, OR, XOR (exclusive-or), and NOT. Unlike the arithmetic operations, a hexadecimal calculator isn't necessary to perform these operations. It is often easier to do them by hand than to use an electronic device to compute them. The logical AND operation is a dyadic1 operation (meaning it accepts exactly two operands). These operands are single binary (base 2) bits. The AND operation is:
0 and 0 = 0
0 and 1 = 0
1 and 0 = 0
1 and 1 = 1
A compact way to represent the logical AND operation is with a truth table. A truth table takes the following form:
Table 5: AND Truth Table AND 0 1 0 0 0 1 0 1
This is just like the multiplication tables you encountered in elementary school. The values in the left column correspond to the leftmost operand of the AND operation. The values in the top row correspond to the rightmost operand of the AND operation. The value located at the intersection of the row and column (for a particular pair of input values) is the result of logically ANDing those two values together.
In English, the logical AND operation is, "If the first operand is one and the second operand is one, the result is one; otherwise the result is zero." We could also state this as "If either or both operands are zero, the result is zero."
One important fact to note about the logical AND operation is that you can use it to force a zero result. If one of the operands is zero, the result is always zero regardless of the other operand. In the truth table above, for example, the row labelled with a zero input contains only zeros and the column labelled with a zero only contains zero results. Conversely, if one operand contains a one, the result is exactly the value of the second operand. These features of the AND operation are very important, particularly when we want to force individual bits in a bit string to zero. We will investigate these uses of the logical AND operation in the next section.
The logical OR operation is also a dyadic operation. Its definition is:
0 or 0 = 0
0 or 1 = 1
1 or 0 = 1
1 or 1 = 1
The truth table for the OR operation takes the following form:
Table 6: OR Truth Table OR 0 1 0 0 1 1 1 1
Colloquially, the logical OR operation is, "If the first operand or the second operand (or both) is one, the result is one; otherwise the result is zero." This is also known as the inclusive-OR operation.
If one of the operands to the logical-OR operation is a one, the result is always one regardless of the second operand's value. If one operand is zero, the result is always the value of the second operand. Like the logical AND operation, this is an important side-effect of the logical-OR operation that will prove quite useful when working with bit strings since it lets you force individual bits to one.
Note that there is a difference between this form of the inclusive logical OR operation and the standard English meaning. Consider the phrase "I am going to the store or I am going to the park." Such a statement implies that the speaker is going to the store or to the park but not to both places. Therefore, the English version of logical OR is slightly different than the inclusive-OR operation; indeed, it is closer to the exclusive-OR operation.
The logical XOR (exclusive-or) operation is also a dyadic operation. It is defined as follows:
0 xor 0 = 0
0 xor 1 = 1
1 xor 0 = 1
1 xor 1 = 0
The truth table for the XOR operation takes the following form:
Table 7: XOR Truth Table XOR 0 1 0 0 1 1 1 0
In English, the logical XOR operation is, "If the first operand or the second operand, but not both, is one, the result is one; otherwise the result is zero." Note that the exclusive-or operation is closer to the English meaning of the word "or" than is the logical OR operation.
If one of the operands to the logical exclusive-OR operation is a one, the result is always the inverse of the other operand; that is, if one operand is one, the result is zero if the other operand is one and the result is one if the other operand is zero. If the first operand contains a zero, then the result is exactly the value of the second operand. This feature lets you selectively invert bits in a bit string.
The logical NOT operation is a monadic operation (meaning it accepts only one operand). It is:
NOT 0 = 1
NOT 1 = 0
The truth table for the NOT operation takes the following form:
Table 8: NOT Truth Table NOT 0 1 1 0
3.8 Logical Operations on Binary Numbers and Bit Strings
As described in the previous section, the logical functions work only with single bit operands. Since the 80x86 uses groups of eight, sixteen, or thirty-two bits, we need to extend the definition of these functions to deal with more than two bits. Logical functions on the 80x86 operate on a bit-by-bit (or bitwise) basis. Given two values, these functions operate on bit zero producing bit zero of the result. They operate on bit one of the input values producing bit one of the result, etc. For example, if you want to compute the logical AND of the following two eight-bit numbers, you would perform the logical AND operation on each column independently of the others:%1011_0101 %1110_1110 ---------- %1010_0100
This bit-by-bit form of execution can be easily applied to the other logical operations as well.
Since we've defined logical operations in terms of binary values, you'll find it much easier to perform logical operations on binary values than on values in other bases. Therefore, if you want to perform a logical operation on two hexadecimal numbers, you should convert them to binary first. This applies to most of the basic logical operations on binary numbers (e.g., AND, OR, XOR, etc.).
The ability to force bits to zero or one using the logical AND/OR operations and the ability to invert bits using the logical XOR operation is very important when working with strings of bits (e.g., binary numbers). These operations let you selectively manipulate certain bits within some value while leaving other bits unaffected. For example, if you have an eight-bit binary value X and you want to guarantee that bits four through seven contain zeros, you could logically AND the value X with the binary value %0000_1111. This bitwise logical AND operation would force the H.O. four bits to zero and pass the L.O. four bits of X through unchanged. Likewise, you could force the L.O. bit of X to one and invert bit number two of X by logically ORing X with %0000_0001 and logically exclusive-ORing X with %0000_0100, respectively. Using the logical AND, OR, and XOR operations to manipulate bit strings in this fashion is known as masking bit strings. We use the term masking because we can use certain values (one for AND, zero for OR/XOR) to `mask out' or `mask in' certain bits from the operation when forcing bits to zero, one, or their inverse.
The 80x86 CPUs support four instructions that apply these bitwise logical operations to their operands. The instructions are AND, OR, XOR, and NOT. The AND, OR, and XOR instructions use the same syntax as the ADD and SUB instructions, that is,and( source, dest ); or( source, dest ); xor( source, dest );
These operands have the same limitations as the ADD operands. Specifically, the source operand has to be a constant, memory, or register operand and the dest operand must be a memory or register operand. Also, the operands must be the same size and they cannot both be memory operands. These instructions compute the obvious bitwise logical operation via the equation:
dest = dest operator source
The 80x86 logical NOT instruction, since it has only a single operand, uses a slightly different syntax. This instruction takes the following form:not( dest );
Note that this instruction has a single operand. It computes the following result:
dest = NOT( dest )
The dest operand (for not) must be a register or memory operand. This instruction inverts all the bits in the specified destination operand.
The following program inputs two hexadecimal values from the user and calculates their logical AND, OR, XOR, and NOT:program LogicalOp; #include( "stdlib.hhf" ); begin LogicalOp; stdout.put( "Input left operand: " ); stdin.get( eax ); stdout.put( "Input right operand: " ); stdin.get( ebx ); mov( eax, ecx ); and( ebx, ecx ); stdout.put( "$", eax, " AND $", ebx, " = $", ecx, nl ); mov( eax, ecx ); or( ebx, ecx ); stdout.put( "$", eax, " OR $", ebx, " = $", ecx, nl ); mov( eax, ecx ); xor( ebx, ecx ); stdout.put( "$", eax, " XOR $", ebx, " = $", ecx, nl ); mov( eax, ecx ); not( ecx ); stdout.put( "NOT $", eax, " = $", ecx, nl ); mov( ebx, ecx ); not( ecx ); stdout.put( "NOT $", ebx, " = $", ecx, nl ); end LogicalOp; Program 3.15 AND, OR, XOR, and NOT Example
1Many texts call this a binary operation. The term dyadic means the same thing and avoids the confusion with the binary numbering system.