An 8-bit barrel shifter must shift its input by 6 positions. The shift amount 6 in binary is 110. Which stages activate?
AOnly the stage that shifts by 6
BThe 4-shift stage (bit 2 = 1) and the 2-shift stage (bit 1 = 1); the 1-shift stage passes through
CThe 4-shift stage and the 1-shift stage; the 2-shift stage passes through
DAll three stages activate since the shift is larger than 4
6 in binary is 110. The 3-bit shift amount controls three stages: bit 2 (value 4) = 1 → the 4-shift stage activates; bit 1 (value 2) = 1 → the 2-shift stage activates; bit 0 (value 1) = 0 → the 1-shift stage passes data through unchanged. Net shift = 4 + 2 = 6. Each stage independently applies or bypasses its power-of-two shift based on the corresponding bit of the shift amount. There is no single stage that shifts by 6 — the logarithmic decomposition means shifts are built from combinations of powers of two.
Question 2 Multiple Choice
A 32-bit barrel shifter uses a logarithmic decomposition. How many mux stages does it require, and how does this compare to a serial shift register performing a 31-position shift?
A32 stages vs. 31 clock cycles — roughly the same cost
B5 stages (log₂ 32) completing in 1 cycle vs. 31 clock cycles
C5 stages but requiring 5 clock cycles vs. 31 clock cycles — a 6x speedup
D32 stages each taking one half-cycle vs. 31 clock cycles — a slight speedup
A 32-bit barrel shifter uses log₂(32) = 5 mux stages, all operating combinationally in a single clock cycle. A serial shift register must clock through one position at a time, requiring 31 clock cycles for a 31-position shift. The barrel shifter is 31x faster for the worst case. The cost is area: 32 × 5 = 160 multiplexers vs. 32 flip-flops for the shift register. This area-for-speed tradeoff is why barrel shifters appear inside processors where shift instructions must complete in a single cycle, while serial registers are used in lower-cost applications where speed is less critical.
Question 3 True / False
A barrel shifter requires multiple clock cycles to complete a shift — more cycles for larger shift amounts.
TTrue
FFalse
Answer: False
The barrel shifter's defining advantage is that it performs any shift in a single clock cycle, regardless of the shift amount. All stages operate combinationally in parallel: every mux in every stage evaluates simultaneously, and the result propagates through all log₂(n) stages in one pass before the clock edge. This is the entire point of the design — trading area (many more multiplexers than a serial register) for speed (constant one-cycle latency). A serial shift register requires one cycle per position shifted, making it O(n) cycles for an n-position shift.
Question 4 True / False
The number of multiplexer stages in an n-bit barrel shifter grows as log₂(n), making the hardware cost scale sublinearly with word width.
TTrue
FFalse
Answer: True
An n-bit barrel shifter uses log₂(n) stages because the shift amount can be decomposed into log₂(n) binary bits, each controlling one stage. A 32-bit shifter uses 5 stages; a 64-bit shifter uses 6 — doubling the word width adds only one stage. The total multiplexer count is n × log₂(n) (n muxes per stage, log₂(n) stages), which grows slower than linearly in terms of stages. This logarithmic stage count is also why the propagation delay is O(log₂ n) mux delays rather than O(n), enabling the single-cycle operation.
Question 5 Short Answer
Explain why the logarithmic decomposition strategy used in a barrel shifter makes it both faster than a serial shifter and more area-expensive. What is the fundamental tradeoff?
Think about your answer, then reveal below.
Model answer: A barrel shifter decomposes any shift into at most log₂(n) power-of-two shifts, each handled by one layer of multiplexers that all evaluate simultaneously in a single clock cycle. This combinational parallelism eliminates the need for sequential clocking: instead of shifting one position per cycle, all the required shifting happens at once through cascaded mux layers. The speed comes from this parallelism. The area cost comes from building all the mux hardware upfront — n × log₂(n) multiplexers compared to a serial register's n flip-flops. The tradeoff is: more transistors at rest (area) in exchange for fewer clock cycles in operation (speed).
This tradeoff is a recurring theme in computer architecture: you can often exchange space for time (pipelining, caching, barrel shifting) or time for space (serial protocols, compression). The barrel shifter is a clean example because the decomposition is exact and the area cost is precisely quantifiable. Processors pay the area cost because shift instructions appear in critical paths and must complete in a single cycle; embedded microcontrollers may instead use serial shifters to save die area.