CHOMPING AT THE BITS
The two assembly language mnemonics I
find most confusing are AND and OR. I
gather these two statements manipulate
data at the bit level, not the byte level. But
all the assembly language books I have
seen tell me only that these mnemonics
perform "logical" ANDs and ORs on the
operands--no great help to novices who
aren't even sure what that means.
What do AND and OR do?
Gerald A. Monroe
Lakewood, Ohio
Logical operations such as AND and OR
represent the fundamental building blocks
of digital computers. To get a good feel for
what these operations are all about, let's
begin by discussing bits. A bit is the sim-
plest form of information because it can
exhibit only one of two states. You can
think of a bit as being either Yes or No, On
or Off, True or False, 1 or 0.
Although the subject of bits and logical
operations is sometimes approached in an
abstract mathematical manner, bits are
very real. In the hardware of digital com-
puters, such as the PC, virtually every in-
terconnection is a "bit carrier." The
wires, the connections between chips on
the circuit boards, the connections within
the chips themselves--all these connec-
tions carry signals in the form of a voltage.
This voltage represents a bit. In much of
the hardware of the PC, a 1 bit is rep-
resented by a 5-volt signal and a 0 bit is rep-
resented by a zero-volt signal.
For instance, the 8088 microprocessor
chip in the PC and PC-XT has 20 pins that
are used to address the memory chips. If
you were able to "freeze" the operation of
the PC and use a voltmeter to measure the
voltages on these 20 pins, you would find
that each pin would measure either 0 volts
(approximately) or 5 volts (approximate-
ly). From these measurements you could
then figure out the 20-bit address the 8088
was outputting to the memory chips.
The various integrated circuit chips on
the board manipulate or process data in
the form of bits. They receive signals from
other chips and send signals out to other
chips. Regardless of the complexity of
these chips, they all contain transistors
wired together into small fundamental
"logic gates." These gates take two input
signals (i.e., two bits) and create from
them an output signal (another bit).
One simple logic gate is called the OR
gate. The input to this gate consists of two
signals (call them A and B), each of which
can be either a 0 or a 1. The output is a 1 if
either A or B is 1. You can represent this
by a formula:
A OR B
You can summarize what an OR gate does
with a small table. This table (and the oth-
ers like it in this article) read from left to
right as follows: For line 1, if the A state is
0 and the B state is 0, then the result of A
OR B is 0. For line 2, if the state of A is 0
and the state of B is 1, then the result of A
OR B is 1, and so on.
A B A OR B
--- --- --------
0 0 0
0 1 1
1 0 1
1 1 1
In theory, only two transistors are re-
quired to construct an OR gate. You can
think of the transistors as switches, one for
each of the inputs. The transistors are
wired in parallel so that the output is on (a
1 bit) if either switch is turned on.
A second simple gate is called the AND
gate. The output to this gate is a 1 only if
both inputs are 1. Here's the formula:
A AND B
Here's the table:
A B A AND B
--- --- ---------
0 0 0
0 1 0
1 0 0
1 1 1
This gate can also be constructed (in
theory) from only two transistors, where
the two transistors are wired in series.
Like switches that are wired in series, the
output will be on (a 1 bit) only if both
switches are turned on.
Another important (although seemingly
trivial) logical operator is called NOT.
This takes one input, which I'll call A. If
A is a 0, NOT changes it to a 1. If A is a 1,
then NOT changes it to a 0:
A NOT A
--- -------
0 1
1 0
Within an integrated circuit, the output
from an OR gate can be the input to a
NOT, so they can function together as rep-
resented by this formula:
NOT (A OR B)
This is called a NOR gate, so we can also
represent this as
A NOR B
Here's what its table looks like:
A B A NOR B
--- --- ---------
0 0 1
0 1 0
1 0 0
1 1 0
The result is simply an inversion of the OR
table results--the 0's in the OR table are
1's in the NOR table, and 1's in the OR ta-
ble become 0's in the NOR table.
Similarly, an output from an AND gate
can feed into a NOT to construct a NAND
gate. The formula
A NAND B
is the same as
NOT (A AND B)
and has the following table:
A B A NAND B
--- --- ----------
0 0 1
0 1 1
1 0 1
1 1 0
You may start to see some relationships be-
tween all these tables. For instance, if you
turn the third column of the OR table up-
side down, it looks like the third column of
the NAND table. That leads to the conclu-
sion that
A OR B = (NOT A) NAND (NOT B)
Similarly,
A AND B = (NOT A) NOR (NOT B)
TEACHING TRANSISTORS TO ADD
Let me stress again that these logical oper-
ations are not solely mathematical exer-
cises but actually perform vital functions in
the PC's hardware. The transistors in the
integrated circuits are wired together to
form little logic gates. The individual logic
gates are wired together to do more-com-
plex tasks, often within the same chip.
I want to demonstrate this real-life ap-
plicability. As you know, a computer can
add two numbers together. We take this for
granted nowadays, but once you start
looking at the computer in terms of logic
gates, it no longer seems trivial. How can
transistors add?
You first must wire together an OR
gate, an AND gate, and a NAND gate. You
start with two inputs and run them into
both the OR gate and the NAND gate. The
output from the OR gate and the output
from the NAND gate become the inputs to
the AND gate. The connection can be
symbolized by the formula
(A OR B) AND (A NAND B)
This is called an "exclusive OR" gate, of-
ten abbreviated XOR. Instead of writing
out the whole expression, we can use
A XOR B
The table summarizing the XOR gate is
shown below:
A B A XOR B
--- --- ---------
0 0 0
0 1 1
1 0 1
1 1 0
You'll notice that this table is similar to
that for the OR gate except that when both
A and B are 1, the result is a 0. What
makes the XOR gate interesting is that it
seems to add the two bits together.
When you're working with a couple of
bits, you can add the two of them together
as shown in the following examples:
0 0 1 1
+0 +1 +0 +1
-- -- -- --
0 1 1 10
In the last example, the result is two bits
long because of a carry bit. The rightmost
digit in each example is the result of an
XOR operation. Notice also that the carry
bit is a result of an AND operation between
the two bits. Thus, we can write formulas
for the SUM bit (the rightmost digit) and
the CARRY bit as follows:
SUM = A XOR B
CARRY = A AND B
We're definitely on the right track. Now
let's take a big step and add together two
4-bit numbers. We'll use 3 and 6 as an ex=
ample. The addition (shown in both deci-
mal and binary form) is shown below:
3 0011
+ 6 + 0110
--- ------
9 1001
When we add multidigit binary numbers
together, we start from the rightmost (least
significant) pair of bits and proceed to the
left, just as we do when we add together
multidigit decimal numbers. However, we
also have to take account of the various
carry bits. When we add a pair of bits, we
also have to add in the carry bit from the
previous calculation. We'll call this the
CARRY-IN bit. The calculation may also
result in a bit to carry into the next calcula-
tion. We'll call this the CARRY-OUT bit.
The CARRY-OUT bit from one calculation
becomes the CARRY-IN bit for the next
calculation.
Because of this carry bit, the formulas
become a little more complex:
SUM = (A XOR B) XOR (CARRY-IN)
CARRY-OUT = (A AND B) XOR ((A XOR B)
AND (CARRY-IN))
Regardless of their increasing complexity,
these formulas still involve only combina-
tions of various logic gates that are built
from transistors.
To do the full addition, you start with
the rightmost pair of bits and do both cal-
culations, then proceed to the next pair of
bits to the left. If you want to verify that
these formulas work for the calculation
shown above, you can put together a table
that shows the bits to be added, the SUM
from each calculation, the CARRY-OUT
from the calculation, and the CARRY-IN
from the previous calculation:
CARRY-IN: 1 1 0 0
A: 0 0 1 1
B: 0 1 1 0
SUM: 1 0 0 1
CARRY-OUT: 0 1 1 0
Human beings may require several
minutes to plug the bits into the formulas
and determine the final result. Transistors
do it in well under a millionth of a second.
But don't feel bad. Human beings were re-
quired to "teach" the transistors how to
add in the first place.
LOGICAL OPERATIONS When pro-
gramming in 8086/8088 assembly lan-
guage, you can take advantage of the mi-
croprocessor's addition hardware using
the ADD, ADC (add with carry), SUB
(subtract), and SBB (subtract with bor-
row) instructions. Since everyone is famil-
iar with addition and subtraction using
numbers, these instructions present few
problems, even for beginners.
But the operations that are more funda-
mental to the inner architecture of the
computer--the AND, OR, NOT, and XOR
instructions--have a more tenuous con-
nection with common life. You may say "I
will take my umbrella if it looks as if it's
going to rain AND I plan to be outside for a
long time." But you'd be pretty weird if
you sat down and drew up a little table of
0's and 1's to determine if an umbrella
were indeed required for your excursion.
When you see the AND, OR, NOT, and
XOR instruction in assembly language,
they work on 8 or 16 bits at a shot. Let's
look at some examples using 8-bit bytes.
I'll be showing bytes in binary notation
with a series of eight 0's and 1's. The Mac-
ro Assembler requires that a "B" follow
such numbers.
Here's the first example:
MOV AL, 01100011B
NOT AL
The first statement moves the value
of 01100011B into register AL. The second
statement performs a NOT operation on
that register. After these two statements,
the value of AL will be 10011100B. The
NOT operator simply changes each 0 bit to
a 1 and each 1 bit to a 0.
In these two statements, a value is
moved into register AL, and then the OR
statement performs a logical OR operation
between that byte and the byte
00110110B:
MOV AL, 01100011B
OR AL, 00110110B
After the second statement, the contents of
the AL register will be 01110111B. Look
at each pair of bits separately. The result is
a 1 only if the bits in either the original val-
ue or the ORed value are 1. That's how we
defined the OR logical operation earlier in
the discussion.
These two statements do the same
thing, except that they use the AND state-
ment:
MOV AL, 01100011B
AND AL, 00110110B
The result in the AL register after perform-
ing the second statement is 00100010B.
Once again, the instruction ANDed each
pair of bits.
This is the XOR:
MOV AL, 01100011B
XOR AL, 00110110B
The result is 01010101B. I showed above
how the XOR logical operator is used for
addition. When you use an XOR statement
in assembly language, however, it doesn't
add the two bytes together because it
doesn't take account of the carry bits.
Each pair of bits is XORed independently
of the others.
THE MASKED BIT Assembly language
programs often use various bits within the
same byte or word to store several pieces
of data. For instance, when the PC's BIOS
stores information about the states of the
shift keys (a subject discussed in PC Tutor,
Volume 6 Number 4), it uses only one byte.
Each of the shift keys can be either up or
down, so only 1 bit is required to describe
each key. While the PC BIOS could cer-
tainly use a separate byte to store the shift
states for each key, that would be a waste of
space.
When working with bit-encoded data,
the use of a "bit mask" is often helpful.
This aids in determining the state of a par-
ticular bit.
For instance, suppose you have a byte
stored in register AL and you want to de-
termine whether the third bit from the right
is a 0 or a 1. If the bit is a 0, you want to
branch off to someplace else in the pro-
gram. If the bit is a 1, you want to coninue
processing. The bit mask you would use is
00000100B. This byte has a 1 only in the
third bit position from the right. You can
use this bit mask in the following sequence
of statements:
AND AL, 00000100B
JZ BitIsOff
When you perform a logical AND between
the byte in AL and 00000100B, all the bits
in AL are set to 0 except the 3rd bits from
the right. The 3rd bit from the right re-
mains unaltered. The Zero Flag would be
set (and the program would branch) only if
this bit were originally a 0.
Using the AND statement for this job
has a little drawback, however--it de-
stroys the value of the original byte in AL.
To retain the original value of AL, you
would instead use the TEST statement
TEST AL, 00000100B
JZ BitIsOff
This sets the Zero Flag if the third bit in AL
is a 0 but doesn't destroy the original con-
tents of the AL register.
You can also use logical operations to
turn individual bits on or off. For instance,
if you wanted to set the third bit in AL to 1,
you would use
OR AL, 00000100B
All bits remain unaltered except the third
bit from the right, which becomes a 1. Sim-
ilarly, if you wanted to set the third bit to 0,
you would use
AND AL, 11111011B
Again, all bits remain unaltered except the
third bit from the right, which here be-
comes a 0. If you wanted to invert the state
of the third bit (turn it from a 0 to a 1 or
from a 1 to a 0), use this:
XOR AL, 00000100B
The ability of XOR to invert bits also
makes it useful in some graphics video ani-
mation. The first XOR draws a figure on
the display by inverting display bits. A sec-
ond XOR reinverts the display bits, effec-
tively erasing the figure and restoring the
appearance of the original display.
© Charles Petzold, 1987, code@charlespetzold.com
This page last updated September, 1999.