2.11 Shifts and Rotates

2.11 Shifts and Rotates

Another set of logical operations that 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 (Figure 2-8 provides an example of an 8-bit shift).

Figure 2-8: Shift Left Operation.

Bit zero moves into bit position one, the previous value in bit position one moves into bit position two, and so on. There are, of course, two questions that naturally arise: "What goes into bit zero?" and "Where does the high order bit wind up?" We'll shift a zero into bit zero and the previous value of the high order bit will become 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

 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 8-bit operands, n=15 for 16-bit operands, and n=31 for 32-bit operands). The dest operand is a typical destination operand; it can be either a memory location or a register.

When the count operand is the constant one, the shl instruction does the operation shown in Figure 2-9.

Figure 2-9: Shift Left Operation.

In Figure 2-9, the "C" represents the carry flag. That is, the H.O. bit shifted out of the operand moves 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.

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) 

Because 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. For a byte value, bit seven moves into bit 6, bit 6 moves into bit 5, bit 5 moves into bit 4, and so on. During a right shift, we'll move a zero into bit 7, and bit 0 will be the carry-out of the operation (see Figure 2-10).

Figure 2-10: Shift Right Operation.

As you would probably expect, 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 0 is shifted into the carry flag. If you specify a count of one, the shr instruction does the operation shown in Figure 2-11.

Figure 2-11: Shift Right Operation.

Once again, Intel's documents suggest that shifts of more than one bit leave the carry in an undefined state.

Because 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 2ⁿ.

There is one problem with shift rights with respect to division: A shift right is only equivalent to an unsigned division by two. For example, if you shift the unsigned representation of 254 ($FE) one place to the right, you get 127 ($7F), exactly what you would expect. However, if you shift the binary representation of −2 ($FE) to the right one position, you get 127 ($7F), which is not correct. This problem occurs because we're shifting a zero into bit 7. If bit 7 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.^[6] 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 the high order bit, an arithmetic shift right operation copies the high order bit back into itself, that is, during the shift operation it does not modify the high order bit, as Figure 2-12 shows.

Figure 2-12: Arithmetic Shift Right Operation.

An arithmetic shift right generally produces the result you expect. For example, if you perform the arithmetic shift right operation on −2 ($FE) you get −1 ($FF). Keep one thing in mind about arithmetic shift right, however. This operation always rounds the numbers to the closest integer that 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 toward zero. But this simply isn't the case. For example, if you apply the arithmetic shift right operation on −1 ($FF), the result is −1, not zero. Minus one is less than zero, so the arithmetic shift right operation rounds toward −1. This is not a "bug" in the arithmetic shift right operation; it just uses a different (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 operates as shown in Figure 2-13 if the count is one.

Figure 2-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. Figures 2-14 and 2-15 diagram these operations.

Figure 2-14: Rotate Left Operation.

Figure 2-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, these 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 Figures 2-16 and 2-17 show.

Figure 2-16: ROL( 1, Dest ) Operation.

Figure 2-17: ROR( 1, Dest ) Operation.

Note that, Intel's documents suggest that rotates of more than one bit leave the carry in an undefined state.

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 rotation shown in Figures 2-18 and 2-19.

Figure 2-18: RCL( 1, Dest ) Operation.

Figure 2-19: RCR( 1, Dest ) Operation.

Again, Intel's documents suggest that rotates of more than one bit leave the carry in an undefined state.

^[6]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.