Microprocessor Design/Shift and Rotate Blocks

From Wikibooks, open books for an open world
Jump to: navigation, search

Shift and Rotate[edit]

Shift and rotate blocks are essential elements in most processors. They are useful on their own, but they also are used in multiplication and division modules. In a binary computer, a left shift has the same effect as a multiplication by 2, and a right shift has the same effect as a division by 2. Since shift and rotate operations perform much more quickly then multiplication and division, they are useful as a tool in program optimization.

Logical Shift[edit]

Rotate left logically.svg Rotate right logically.svg
A left logical shift A right logical shift

In a logical shift, the data is shifted in the appropriate direction, and a zero is shifted into the new location.

Arithmetic shift[edit]

Rotate right arithmetically.svg
A right arithmetic shift

In an arithmetic shift, the data is shifted right so that the sign of the data item is preserved. This means that the MSB is the value that is shifted into the new position. An arithmetic left shift is the same as a logical left shift, and is therefore not shown here.

Rotations[edit]

Rotate left.svg Rotate right.svg
A left rotation A right rotation

A rotation is like a shift, except the bit shifted off the end of the register is then shifted into the new spot.

Fast Shift Implementations[edit]

The above images in each section help to indicate a method to shift a register more quickly, at the expense of requiring additional hardware. Instead of having one register that attempts to shift in place, we have have two registers in parallel, with wires connecting the various blocks together. When a shift is indicated, gates open that allow the data to pass from one register to the next, the proper number of spaces forward or backward.

In practice, fast shift blocks are implemented as a "barrel shifter". The barrel shifter includes several "levels" of multiplexers, each connected to the previous one by straight wires (wires that transfer the data without a shift), and wires that cause a shift by successive powers of two. For instance, the first level of shift would be 4 spaces, the next level would be 2 spaces, and the last level would be 1 space. In this way, the value of each shift level corresponds to the binary representation of the number of spaces to shift. This implementation makes for very fast shifters that can shift an arbitrary number of spaces in a single clock cycle.

Further reading[edit]

32-Bit Barrel Shifter Implementation Using 74-Series Integrated Circuits