Barrel shifters

A barrel shifter is a combinational circuit that shifts (or rotates) a data word by any number of bit positions in one clock cycle, using only multiplexers — no clocking, no iteration.

The Core Idea

WHY do we need it?

Processors execute instructions like SHL R1, 5 or floating-point normalisation, address scaling, and multiply/divide-by-powers-of-2 — every cycle. A multi-cycle shifter would stall the pipeline. We want a single-cycle, purely combinational device.

WHAT is it, precisely?

HOW is it structured?

The key insight: decompose the shift amount into bits.

$S = \sum_{i=0}^{k-1} s_i \, 2^i, \qquad k = \log_2 n$

• Stage $i$ is controlled by bit $s_i$.
• If $s_i = 1$, stage $i$ shifts its input by $2^i$; if $s_i = 0$, it passes data through unchanged.
• Cascade all $k$ stages → total shift $= \sum s_i 2^i = S$. ✅

Deriving the multiplexer equation from scratch

Consider stage $i$, which shifts left by $2^i$ when $s_i=1$ (fill with 0s). Let the stage input be $A = a_{n-1}\dots a_0$ and output $B = b_{n-1}\dots b_0$.

What does "left shift by $2^i$" mean? Output bit $j$ takes input bit $j - 2^i$: $b_j = a_{j-2^i}\quad(\text{and } b_j = 0 \text{ if } j - 2^i < 0)$

When $s_i = 0$, pass through: $b_j = a_j$.

Combine both cases with a 2:1 mux selected by $s_i$:

For a rotate, the bits that fall off the end wrap around instead of being replaced by 0: $b_j = \overline{s_i}\,a_j + s_i\,a_{(j-2^i)\bmod n}$

Counting the hardware (the 80/20 that matters)

• Number of stages $= ==\log_2 n==$.
• Each stage has $n$ muxes (one per output bit).
• Total muxes $= ==n\log_2 n==$.
• Propagation delay $= ==\log_2 n== \times (\text{delay of one 2:1 mux})$ — grows only logarithmically, which is why it's fast.

Worked Example 1 — Shift left by 13 on an 8… wait, 16-bit word

Take $n = 16$, so $k = \log_2 16 = 4$ stages (shift by 1, 2, 4, 8). Shift amount $S = 13$.

Step 1 — write $S$ in binary. $13 = 1101_2$, so $s_3 s_2 s_1 s_0 = 1101$. Why? The control bits ARE the binary digits of the shift amount.

Step 2 — turn on the matching stages.

• $s_0 = 1$ → shift by $2^0 = 1$
• $s_1 = 0$ → pass through
• $s_2 = 1$ → shift by $2^2 = 4$
• $s_3 = 1$ → shift by $2^3 = 8$

Step 3 — total shift $= 1 + 4 + 8 = 13$. ✅ Why this step? Confirms the sum-of-powers decomposition equals the requested shift.

Trace with input A = 0000 0000 0000 0001 (value 1):

• After stage 0 (shift 1): ...0010
• Stage 1 (pass): ...0010
• Stage 2 (shift 4): ...0010 0000
• Stage 3 (shift 8): 0010 0000 0000 0000 = $2^{13} = 8192$. ✅ ($1 \times 2^{13}$.)

Worked Example 2 — Rotate right by 3 on a 4-bit word

$n=4$, $k=2$ stages. Rotate-right amount $S=3 = 11_2$, so $s_1 s_0 = 11$: rotate by 1 then by 2.

Input $A = 1000$ (bit 3 set).

• Rotate right by 1 → 0100 Why? $b_j = a_{(j+1)\bmod 4}$; bit that leaves bottom wraps to top.
• Rotate right by 2 → 0001 Why? Applying the mod-wrap again by $2^1=2$.

Total rotate-right by 3 of 1000 = 0001. Check directly: rotating 1000 right 3 = 0001. ✅

Common Mistakes

Active Recall

Connections

• Multiplexers — the fundamental building block (2:1 mux per bit).
• Binary Number Representation — decomposition of shift amount into powers of two.
• Combinational Circuits — no clock, purely input-driven.
• Shift and Rotate Operations — the ALU operations this implements.
• Logarithmic Delay Structures — same $\log n$ idea as carry-lookahead / prefix networks.
• Floating Point Normalization — a major real user of fast shifters.

Concept Map

Hinglish (regional understanding)