THE INSTRUCTION SET ARCHITECTURE LEVEL - Structured Computer Organization - page 389

it means that a negative number will remain negative. This situation is illustrated
below for 2-bit right shifts.
11111111 11111111 11111111 11110000 A
00111111 11111111 11111111 11111100 A shifted without sign extension
11111111 11111111 11111111 11111100 A shifted with sign extension
An important use of shifting is multiplication and division by powers of 2. If a
positive integer is left shifted k bits, the result, barring overflow, is the original
number multiplied by 2 k . If a positive integer is right shifted k bits, the result is the
original number divided by 2 k .
Shifting can be used to speed up certain arithmetic operations. Consider, for
example, computing 18 × n for some positive integer n . Because 18 × n =

16 × n + 2 × n ,16 × n can be obtained by shifting a copy of n 4 bits to the left.

2 n can be obtained by shifting n 1 bit to the left. The sum of these two numbers

is 18

×

n . The multiplication has been accomplished by a move, two shifts, and an
addition, which is often faster than a multiplication. Of course, the compiler can
use this trick only when one factor is a constant.
Shifting negative numbers, even with sign extension, gives quite different re-
sults, however. Consider, for example, the ones' complement number,

×

− 1. Shifted

1 bit to the left it yields − 3. Another 1-bit shift to the left yields − 7:

11111111 11111111 11111111 11111110 − 1 in ones' complement

11111111 11111111 11111111 11111100 − 1 shifted left 1 bit = − 3

7
Left shifting ones' complement negative numbers does not multiply by 2. Right
shifting does simulate division correctly, however.
Now consider a two's complement representation of

11111111 11111111 11111111 11111000 − 1 shifted left 2 bits = −

− 1. When right shifted 6

bits with sign extension, it yields − 1, which is incorrect because the integral part of

− 1/64 is 0:

11111111 11111111 11111111 11111111 − 1 in two's complement

1
In general, right shifting introduces errors because it truncates down (toward the
more negative integer), which is incorrect for integer arithmetic on negative num-
bers. Left shifting does, however, simulate multiplication by 2.
Rotate operations are useful for packing and unpacking bit sequences from
words. If it is desired to test all the bits in a word, rotating the word 1 bit at a time
either way successively puts each bit in the sign bit, where it can be easily tested,
and also restores the word to its original value when all bits have been tested. Ro-
tate operations are more pure than shift operations because no information is lost:
an arbitrary rotate operation can be negated with another rotate operation.
Certain dyadic operations occur so frequently with particular operands that
ISAs sometimes have monadic instructions to accomplish them quickly. Moving

11111111 11111111 11111111 11111111 − 1 shifted right 6 bits = −