3.11 Shifts and Rotates
Another set of logical operations which apply to bit strings are the shift and rotate operations. These two categories can be further broken down into left shifts, left rotates, right shifts, and right rotates. These operations turn out to be extremely useful to assembly language programmers.
The left shift operation moves each bit in a bit string one position to the left (see Figure 3.8).
Figure 3.8 Shift Left Operation
Bit zero moves into bit position one, the previous value in bit position one moves into bit position two, etc. There are, of course, two questions that naturally arise: "What goes into bit zero?" and "Where does bit seven wind up?" We'll shift a zero into bit zero and the previous value of bit seven will be the carry out of this operation.
The 80x86 provides a shift left instruction, SHL, that performs this useful operation. The syntax for the SHL instruction is the following:
shl( count, dest );The count operand is either "CL" or a constant in the range 0..n, where n is one less than the number of bits in the destination operand (i.e., n=7 for eightbit operands, n=15 for 16bit operands, and n=31 for 32bit operands). The dest operand is a typical dest operand, it can be either a memory location or a register.
When the count operand is the constant one, the SHL instruction does the following:
Figure 3.9 Operation of the SHL( 1, Dest) Instruction
In Figure 3.9, the "C" represents the carry flag. That is, the bit shifted out of the H.O. bit of the operand is moved into the carry flag. Therefore, you can test for overflow after a SHL( 1, dest ) instruction by testing the carry flag immediately after executing the instruction (e.g., by using "if( @c ) then..." or "if( @nc ) then...").
Intel's literature suggests that the state of the carry flag is undefined if the shift count is a value other than one. Usually, the carry flag contains the last bit shifted out of the destination operand, but Intel doesn't seem to guarantee this. If you need to shift more than one bit out of an operand and you need to capture all the bits you shift out, you should take a look at the SHLD and SHRD instructions in the appendicies.
Note that shifting a value to the left is the same thing as multiplying it by its radix. For example, shifting a decimal number one position to the left ( adding a zero to the right of the number) effectively multiplies it by ten (the radix):
1234 shl 1 = 12340 (shl 1 means shift one digit position to the left)Since the radix of a binary number is two, shifting it left multiplies it by two. If you shift a binary value to the left twice, you multiply it by two twice (i.e., you multiply it by four). If you shift a binary value to the left three times, you multiply it by eight (2*2*2). In general, if you shift a value to the left n times, you multiply that value by 2n.
A right shift operation works the same way, except we're moving the data in the opposite direction. Bit seven moves into bit six, bit six moves into bit five, bit five moves into bit four, etc. During a right shift, we'll move a zero into bit seven, and bit zero will be the carry out of the operation (see Figure 3.10).
Figure 3.10 Shift Right Operation
As you would probably expect by now, the 80x86 provides a SHR instruction that will shift the bits to the right in a destination operand. The syntax is the same as the SHL instruction except, of course, you specify SHR rather than SHL:
SHR( count, dest );This instruction shifts a zero into the H.O. bit of the destination operand, it shifts all the other bits one place to the right (that is, from a higher bit number to a lower bit number). Finally, bit zero is shifted into the carry flag. If you specify a count of one, the SHR instruction does the following:
Figure 3.11 SHR( 1, Dest ) Operation
Once again, Intel's documents suggest that shifts of more than one bit leave the carry in an undefined state.
Since a left shift is equivalent to a multiplication by two, it should come as no surprise that a right shift is roughly comparable to a division by two (or, in general, a division by the radix of the number). If you perform n right shifts, you will divide that number by 2n.
There is one problem with shift rights with respect to division: as described above a shift right is only equivalent to an unsigned division by two. For example, if you shift the unsigned representation of 254 (0FEh) one place to the right, you get 127 (07Fh), exactly what you would expect. However, if you shift the binary representation of 2 (0FEh) to the right one position, you get 127 (07Fh), which is not correct. This problem occurs because we're shifting a zero into bit seven. If bit seven previously contained a one, we're changing it from a negative to a positive number. Not a good thing when dividing by two.
To use the shift right as a division operator, we must define a third shift operation: arithmetic shift right^{1}. An arithmetic shift right works just like the normal shift right operation (a logical shift right) with one exception: instead of shifting a zero into bit seven, an arithmetic shift right operation leaves bit seven alone, that is, during the shift operation it does not modify the value of bit seven as Figure 3.12 shows.
Figure 3.12 Arithmetic Shift Right Operation
This generally produces the result you expect. For example, if you perform the arithmetic shift right operation on 2 (0FEh) you get 1 (0FFh). Keep one thing in mind about arithmetic shift right, however. This operation always rounds the numbers to the closest integer which is less than or equal to the actual result. Based on experiences with high level programming languages and the standard rules of integer truncation, most people assume this means that a division always truncates towards zero. But this simply isn't the case. For example, if you apply the arithmetic shift right operation on 1 (0FFh), the result is 1, not zero. 1 is less than zero so the arithmetic shift right operation rounds towards minus one. This is not a "bug" in the arithmetic shift right operation, it's just uses a diffferent (though valid) definition of integer division.
The 80x86 provides an arithmetic shift right instruction, SAR (shift arithmetic right). This instruction's syntax is nearly identical to SHL and SHR. The syntax is
SAR( count, dest );The usual limitations on the count and destination operands apply. This instruction does the following if the count is one:
Figure 3.13 SAR(1, dest) Operation
Once again, Intel's documents suggest that shifts of more than one bit leave the carry in an undefined state.
Another pair of useful operations are rotate left and rotate right. These operations behave like the shift left and shift right operations with one major difference: the bit shifted out from one end is shifted back in at the other end.
Figure 3.14 Rotate Left Operation
Figure 3.15 Rotate Right Operation
The 80x86 provides ROL (rotate left) and ROR (rotate right) instructions that do these basic operations on their operands. The syntax for these two instructions is similar to the shift instructions:
rol( count, dest ); ror( count, dest );Once again, this instructions provide a special behavior if the shift count is one. Under this condition these two instructions also copy the bit shifted out of the destination operand into the carry flag as the following two figures show:
Figure 3.16 ROL( 1, Dest) Operation
Note that, Intel's documents suggest that rotates of more than one bit leave the carry in an undefined state.
Figure 3.17 ROR( 1, Dest ) Operation
It will turn out that it is often more convenient for the rotate operation to shift the output bit through the carry and shift the previous carry value back into the input bit of the shift operation. The 80x86 RCL (rotate through carry left) and RCR (rotate through carry right) instructions achieve this for you. These instructions use the following syntax:
RCL( count, dest ); RCR( count, dest );As is true for the other shift and rotate instructions, the count operand is either a constant or the CL register and the destination operand is a memory location or register. The count operand must be a value that is less than the number of bits in the destination operand. For a count value of one, these two instructions do the following:
Figure 3.18 RCL( 1, Dest ) Operation
Figure 3.19 RCR( 1, Dest) Operation
Again, Intel's documents suggest that rotates of more than one bit leave the carry in an undefined state.
^{1}There is no need for an arithmetic shift left. The standard shift left operation works for both signed and unsigned numbers, assuming no overflow occurs.
