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, email@example.com
This page last updated September, 1999.