Barrel shifters: Visual walkthrough — Hardware deep dive

This page is the picture version of the parent note. Read it slowly; each step has one figure that is the argument.

Step 1 — What "shift" even looks like

WHAT. Before any circuit, let us agree what a shift does to a row of bits. A word is just a line of boxes, each holding a $0$ or a $1$ . We number the boxes from the right: box $0$ , box $1$ , box $2$ , … The number in a box is its index $j$ . "Shift left by $d$ " means: whatever sat in box $j - d$ now sits in box $j$ . Everything slides toward the high-index (left) end.

WHY. If we cannot say precisely which box copies from which box, we cannot build wires. The whole circuit is nothing but "box $j$ gets its value from box $j - d$ ".

PICTURE. In the figure, the pale-yellow arrows show every bit hopping $d = 1$ box to the left. The box that would need input from box $- 1$ (off the right edge) has no source — so we pour in a $0$ (chalk-pink). That pink zero is the "fill" and it is the heart of the difference between shift and rotate later.

Step 2 — Why not just shift by 1, over and over?

WHAT. The simplest shifter moves everything by exactly one box. To shift by 7, you would feed the output back in and run it 7 times.

WHY IT'S BAD. Each pass costs a clock tick. Shift-by-7 = 7 ticks; shift-by- $d$ = $d$ ticks. A processor shifts every cycle, so a $d$ -cycle shifter would freeze the whole pipeline. We need the answer in one pass — a purely input-driven, no-clock (combinational) device.

PICTURE. The figure stacks the slow machine (a staircase of tiny 1-hops, one per clock, drawn in chalk-blue with a ticking clock) against the goal (one big jump, pale-yellow). The visual contrast — many small stairs vs. one leap — is the entire motivation.

Step 3 — The trick: any distance is a sum of powers of two

WHAT. Instead of jumps of $1$ , allow only jumps that are powers of two: $1, 2, 4, 8, \dots$ Then every distance is built by switching some of these jumps ON and the rest OFF.

WHY THIS WORKS. Every whole number has exactly one binary form — it is a sum of distinct powers of two (Binary Number Representation). Example: $13 = 8 + 4 + 1 = 110 1_{2}$ . So to move $13$ , switch on the $8$ -jump, the $4$ -jump, the $1$ -jump, leave the $2$ -jump off. No number needs two copies of the same jump, which is why one switch per power of two is enough.

PICTURE. The figure shows a row of ON/OFF sliders labelled $1, 2, 4, 8$ . Above each, its binary weight; the ON sliders (pale-yellow, lit) are $8, 4, 1$ and their little jumps chain into one big $13$ -arrow at the bottom.

Step 4 — One switch = one 2-to-1 multiplexer

WHAT. Each ON/OFF slider is, in hardware, a 2-to-1 multiplexer (see Multiplexers). A 2:1 mux is a chalk-drawn "Y": two input wires, one select wire $s$ , one output. When $s = 0$ the top input passes; when $s = 1$ the bottom input passes.

WHY A MUX AND NOT SOMETHING ELSE. We need a device that answers one yes/no question — "do I take the un-shifted bit, or the shifted-by- $2^{i}$ bit?" A 2:1 mux is exactly that question in silicon; nothing simpler chooses between two wires under one control bit.

PICTURE. The figure draws one output bit $b_{j}$ fed by two candidate wires: $a_{j}$ (the "stay put" bit, chalk-blue) into input $D_{0}$ , and $a_{j - 2^{i}}$ (the "shifted" bit, pale-yellow) into input $D_{1}$ . The select line $s_{i}$ tips the switch.

Step 5 — A whole stage is one row of these muxes

WHAT. Stage $i$ is $n$ copies of that mux side by side — one mux per output box — all sharing the same select bit $s_{i}$ . When $s_{i} = 1$ the entire row shifts by $2^{i}$ ; when $s_{i} = 0$ the entire row passes straight through.

WHY. Every output box needs its own decision ("did I get a shifted bit or a stay-put bit?"), but they must all obey the same switch, or the word would tear apart. Hence one shared $s_{i}$ , $n$ muxes.

PICTURE. The figure shows stage $i = 2$ (jump of $4$ ) on a small word: the diagonal pale-yellow wires carry each $a_{j - 4}$ up to box $j$ ; the vertical chalk-blue wires are the $a_{j}$ pass-through path. The boxes at the bottom right ( $j - 4 < 0$ ) are fed chalk-pink $0$ s.

Step 6 — Cascade the stages; the shifts add up

WHAT. Stack the $k$ stages in a column: the output of stage $0$ feeds stage $1$ , whose output feeds stage $2$ , and so on. Stage $i$ contributes $s_{i} 2^{i}$ to the total displacement.

WHY THE SUM COMES OUT RIGHT. Passing a bit through stage after stage just adds each stage's jump. The bits that get through jumps of $8$ , then $4$ , then $1$ have moved $8 + 4 + 1 = 13$ places. That is precisely $S = \sum s_{i} 2^{i}$ — the same sum from Step 3, now realised as a physical stack.

PICTURE. The figure is a vertical cascade for $n = 16$ , $S = 13 = 110 1_{2}$ . Lit stages ( $s_{0}, s_{2}, s_{3}$ , pale-yellow) show their diagonal jumps; the dark stage ( $s_{1} = 0$ , dimmed) is a straight pass-through. A single bit is tracked (chalk-pink dot) from box $0$ to box $13$ .

Step 7 — The degenerate & edge cases (never skip these)

WHAT & WHY & PICTURE. Four scenarios you must be sure about, each drawn in its own panel:

$S = 0$ (shift by nothing). All $s_{i} = 0$ , every stage passes straight through. Output = input. The circuit always has this case — it is the "identity" and costs no extra hardware.
$S = n - 1$ (the maximum). For $n = 16$ , $S = 15 = 111 1_{2}$ : all stages ON. This is the busiest wiring; the picture shows every diagonal lit at once.
Fill vs. wrap at the edge. For a logical shift, boxes with $j - 2^{i} < 0$ take a $0$ (chalk-pink). For a rotate, those same boxes take the bit that fell off — index $(j - 2^{i}) mod n$ (chalk-blue loop-around wire). Same mux, different $D_{1}$ wire.
Order doesn't change the data. Because stages only add displacements, swapping stage order still totals $S$ . The picture shows two orderings landing the same bit in the same box.

Step 8 — Why the whole thing is fast (the payoff)

WHAT. Count the pictures we drew: $k = lo g_{2} n$ stages, each stage $n$ muxes.

WHY IT MATTERS. A signal crosses only $lo g_{2} n$ mux layers top-to-bottom, so delay grows logarithmically — the same $lo g$ trick behind carry-lookahead adders and behind why float normalisation can shift a mantissa in one cycle.

PICTURE. The figure plots the naïve shifter's delay ( $\propto n$ , a steep line) against the barrel shifter's delay ( $\propto lo g_{2} n$ , a nearly flat curve), with $n = 32$ marked: $5$ stages, $160$ muxes.

The one-picture summary

One figure compresses the whole derivation: the binary digits of $S$ on the left flip the stage switches; each ON stage adds its power-of-two jump; the jumps chain into the total displacement $S$ on the right.

Recall Feynman retelling — the whole walkthrough in plain words

Picture a shelf of books you want to slide any number of spaces in one push. You are only allowed helpers who each push by a fixed jump: one pushes by 1, one by 2, one by 4, one by 8. To move the books 13 spaces you switch ON the 8-helper, the 4-helper, and the 1-helper (because $8 + 4 + 1 = 13$ ) and leave the 2-helper off. Each helper is a tiny two-way switch (a multiplexer): OFF means "leave the book where it is", ON means "hand it to the book that's a jump away". Stack the helpers in a column — the book falls through them one after another and lands exactly 13 spaces over. If a book would slide off the right edge, you either drop a blank (a shift) or send it back in from the left (a rotate) — same helpers, just a different wire for the edge. With only 4 helpers you cover every distance from 0 to 15, and a signal only ever crosses 4 layers, which is why the whole thing is lightning fast.

Connections

Multiplexers — the 2:1 mux of Step 4 is the atom of every stage.
Binary Number Representation — Step 3's sum-of-powers is just binary.
Combinational Circuits — no clock; Step 2's motivation.
Shift and Rotate Operations — Step 7's two flavours.
Logarithmic Delay Structures — Step 8's $lo g n$ depth.
Floating Point Normalization — a real consumer of single-cycle shifts.