How Does a Barrel Shifter Work in One Clock Cycle?
A barrel shifter is a combinational digital circuit that shifts or rotates a binary data word by any specified number of bit positions within a single clock cycle. Unlike sequential shift registers that require one clock cycle per bit shifted, a barrel shifter uses layers of multiplexers to route every input bit directly to its target output position in parallel.
Why Sequential Shifting Is Too Slow
In early or area-constrained processors, bit shifting is performed using a shift register. A shift register moves data by one bit position per clock cycle. Shifting a 32-bit word by 16 positions would therefore take 16 clock cycles, stalling the instruction pipeline and degrading processor throughput.
A barrel shifter eliminates this bottleneck by replacing sequential state transitions with pure combinational logic. Because the signal propagates through a fixed number of multiplexer stages without waiting for a clock edge between stages, the entire multi-bit shift completes within a single clock period.
Logarithmic Multiplexer Architecture
For an \(n\)-bit data word, a barrel shifter typically arranges multiplexers in \(\log_2(n)\) stages. Each stage corresponds to a power-of-two shift amount, controlled by a single bit of the shift-amount input \(S\).
For a 32-bit barrel shifter, the shift amount \(S\) is a 5-bit unsigned integer:
\[S = s_4 s_3 s_2 s_1 s_0\]
Each bit \(s_k\) controls stage \(k\), which either passes the data unchanged or shifts it by \(2^k\) positions:
- Stage 0 shifts by \(2^0 = 1\) bit if \(s_0 = 1\).
- Stage 1 shifts by \(2^1 = 2\) bits if \(s_1 = 1\).
- Stage 2 shifts by \(2^2 = 4\) bits if \(s_2 = 1\).
- Stage 3 shifts by \(2^3 = 8\) bits if \(s_3 = 1\).
- Stage 4 shifts by \(2^4 = 16\) bits if \(s_4 = 1\).
Any shift amount from \(0\) to \(31\) can be formed by combining these power-of-two stages. For example, a shift of \(13\) bits (\(13 = 8 + 4 + 1\), so \(S = 01101_2\)) activates stages 3, 2, and 0 while stages 4 and 1 pass their inputs straight through.
Executing Logical and Arithmetic Shifts
The difference between logical shifts, arithmetic shifts, and rotations lies in how the vacated bit positions are filled at each multiplexer stage.
Logical Shifts
In a logical left shift, vacated least significant bits are filled with \(0\). In a logical right shift, vacated most significant bits are filled with \(0\). The multiplexers at each stage simply route a constant \(0\) into the positions that have no corresponding input bit from the shifted direction.
Arithmetic Shifts
An arithmetic right shift preserves the sign of a two's complement signed number. Instead of filling vacated most significant bits with \(0\), the barrel shifter replicates the original sign bit \(x_{n-1}\) into all vacated upper positions. At stage \(k\), if \(s_k = 1\), the top \(2^k\) multiplexer inputs receive \(x_{n-1}\) rather than \(0\).
An arithmetic left shift behaves identically to a logical left shift in terms of bit movement, filling the vacated lower bits with \(0\), though the processor may separately check for signed overflow if the sign bit changes.
Hardware Cost and Timing
Because each of the \(n\) output bits requires a 2-to-1 multiplexer per stage, a logarithmic barrel shifter for an \(n\)-bit word uses \(n \log_2(n)\) 2-to-1 multiplexers. For a 32-bit word, this equals \(32 \times 5 = 160\) multiplexers, and for a 64-bit word, it equals \(64 \times 6 = 384\) multiplexers.
The critical path delay is proportional to \(\log_2(n)\) multiplexer delays plus wiring capacitance. This shallow logic depth allows the barrel shifter to fit comfortably within the execute stage of a modern CPU pipeline, completing any multi-bit logical or arithmetic shift in one clock cycle.