Barrel Shifter
A barrel shifter moves a word left or right by any number of positions in one pass, using layered stages of multiplexers.
Shifting in One Step
A naive shifter that moves one bit per clock cycle would take up to n cycles to shift an n-bit word. A barrel shifter does any shift amount in a single combinational pass. It is a purely wire-and-multiplexer structure with no sequential state.
The trick is binary decomposition of the shift amount. A shift by k is built from stages that shift by 1, 2, 4, 8, and so on. Each stage either passes the data straight through or shifts it by its power-of-two amount, controlled by one bit of the shift count. For an n-bit word this needs log2(n) stages of 2:1 multiplexers.
Log-Depth Construction
To shift a 32-bit value by an arbitrary amount you use five stages controlled by the five bits of the shift amount. Stage 0 shifts by 1 if its control bit is set, stage 1 by 2, stage 2 by 4, and so on. The composed result is a shift by exactly the requested count. Delay grows only as the logarithm of the width.
Rotates and Arithmetic Shifts
A barrel shifter is easily extended. To rotate, bits that fall off one end are wrapped to the other rather than filled with zeros. For an arithmetic right shift, the vacated high bits are filled with copies of the sign bit to preserve the value of a signed number. A funnel shifter concatenates two words and shifts across the boundary, which supports variable-length field extraction.
- log2(n) mux stages, one per bit of the shift amount
- Single-cycle for any shift distance
- Supports logical, arithmetic, and rotate modes
Where It Lives
Every general-purpose CPU has a barrel shifter in its ALU or as a dedicated unit, because shifts and rotates are frequent instructions and appear inside multiply, divide, and floating-point normalization. Cryptographic and hashing hardware leans on rotates heavily, so a fast barrel shifter is essential there too.
The cost is area: the multiplexer network grows as n times log n. For very wide datapaths designers sometimes fold the shifter or share it across lanes, trading a little latency for silicon area.