Worked examples — Barrel shifters

This page is the worked-example drill floor for the barrel-shifter topic. The parent note built the machine; here we run every kind of input through it until no scenario can surprise you. If a symbol looks unfamiliar, the parent note and Multiplexers, Binary Number Representation, Shift and Rotate Operations define it — but every worked case below re-earns what it uses.

---

The scenario matrix

Every case a shift/rotate problem can throw at you falls into one of these cells. The examples afterwards are each tagged with the cell they cover.

#	Case class	What is special about it	Covered by
A	Zero shift ($S=0$)	all sliders OFF — degenerate identity	Ex 1
B	Single power-of-two shift ($S=2^i$)	exactly one slider ON	Ex 2
C	Multi-bit shift ($S$ has several 1-bits)	several sliders ON, sum decomposition	Ex 3
D	Maximum shift ($S=n-1$)	all sliders ON, edge of the range	Ex 4
E	Over-shift / out of range ($S\ge n$)	control width overflow, all bits leave	Ex 5
F	Rotate (wrap-around)	bits wrap instead of vanishing	Ex 6
G	Right vs left direction	index goes $+2^i$ not $-2^i$	Ex 7
H	Real-world word problem	address scaling / multiply-by-power-of-two	Ex 8
I	Exam twist — hardware counting	muxes + delay, not the data	Ex 9
J	Exam twist — arithmetic (sign) shift	vacated bits copy the sign bit, not 0	Ex 10

We use one convention throughout, taken straight from the parent's [!formula] callout:

Here $\overline{s_i}$ means "NOT $s_i$" (the slider is off), $s_i{a}_{j-2^i}$ means "slider on, pull the shifted bit", and $+$ is logical OR — exactly the 2:1 multiplexer equation $\text{out}=\overline{sel}{D}_0+sel{D}_1$.

The figure above shows the four-stage skeleton once, so later examples can just say "stage 2 is ON".

---

Example 1 — Cell A: the zero shift (degenerate identity)

Forecast: guess before reading — does anything move at all?

1. Write $S$ in binary. $n=8\Rightarrow k={\log }_{2}8=3$ control bits. $0=000_2$, so $s_2{s}_1{s}_0=000$. Why this step? The control bits are the binary digits of the shift amount; three bits cover $0$–$7$.
2. Check each slider. $s_0=s_1=s_2=0$ → every stage is in pass-through mode. Why this step? From the formula, $s_i=0$ gives $b_j=\overline{0}{a}_j=a_j$ — the wire just carries the bit straight through.
3. Result: $B=A=10110110$. Why this step? No slider is on, so no displacement is added; $0$ is the identity of "sum of powers of two".

Verify: interpret as a number: $10110110_2=182$. Left shift by 0 = $182\times 2^0=182$. Output $=182$. ✅ The degenerate case just returns the input.

---

Example 2 — Cell B: a single power-of-two shift

Forecast: how many sliders switch on for $S=4$?

1. Binary of $S$. $4=100_2$, so $s_2{s}_1{s}_0=100$. Only stage 2 is ON (it jumps by $2^2=4$). Why this step? $4$ is itself a power of two, so exactly one bit is set — exactly one slider fires.
2. Apply stage 2: $b_j=a_{j-4}$ (fill 0 when $j-4<0$). Why this step? Left shift by 4 pulls each output bit from four positions lower; the bottom four positions have no source, so they become 0.
3. Slide the bits. Input 0000 0011 → the two set bits at positions 0,1 move to positions 4,5: 0011 0000. Why this step? Bit at position $j_{\text{in}}$ lands at $j_{\text{in}}+4$; $0\to 4$, $1\to 5$.

Verify: $3\times 2^4=48$. Output 0011 0000 $=32+16=48$. ✅

---

Example 3 — Cell C: multi-bit shift (sum of powers)

Forecast: which stages light up? Sum them before you read.

1. Binary of $S$. $k={\log }_{2}16=4$. $13=1101_2$, so $s_3{s}_2{s}_1{s}_0=1101$. Why this step? Stages ON = 8, 4, 1; stage 2 (value 4… wait, that is $2^2=4$) — recount: bits set are $s_0(1),s_2(4),s_3(8)$. Sum $=1+4+8=13$. ✅
2. Stage 0 (shift 1): ...0001 → ...0010. Why this step? $s_0=1$ pulls $b_j=a_{j-1}$; the lone bit moves up one.
3. Stage 1 (pass, $s_1=0$): ...0010 unchanged. Why this step? Slider off = wire straight through.
4. Stage 2 (shift 4): ...0010 → ...0010 0000 (bit at pos 1 → pos 5). Why this step? $s_2=1$ pulls $b_j=a_{j-4}$.
5. Stage 3 (shift 8): bit at pos 5 → pos 13: 0010 0000 0000 0000. Why this step? $s_3=1$ pulls $b_j=a_{j-8}$; $5+8=13$.

Verify: $1\times 2^{13}=8192$. Output has a single 1 at position 13 $=8192$. ✅

---

Example 4 — Cell D: the maximum shift $S=n-1$

Forecast: at maximum shift, where does the bottom bit end up — and what fills behind it?

1. Binary of $S$. $7=111_2$, so $s_2{s}_1{s}_0=111$: all three sliders ON (jumps 1+2+4 = 7). Why this step? $n-1$ is the all-ones control pattern — the edge of the addressable range.
2. Cascade: bit at pos 0 → after +1 → pos1 → after +2 → pos3 → after +4 → pos7. Why this step? Displacements add: $0+1+2+4=7$.
3. Fill behind it with 0 (logical shift, vacated indices out of range). Why this step? Rule 1: pulled index $<0$ gives $b_j=0$.

Verify: $1\times 2^7=128$. Output 1000 0000 $=128$. ✅ Maximum single-cycle shift reaches exactly the top bit.

---

Example 5 — Cell E: over-shift beyond the word

Forecast: $9$ needs 4 bits but the control bus is only 3 wide — what gets lost?

1. Control-width overflow. $9=1001_2$ needs 4 bits, but only $s_2{s}_1{s}_0$ exist. The top bit ($8$) has no wire. Why this step? Parent [!mistake]: shift-amount width is $\lceil {\log }_{2}n\rceil =3$, not the data width.
2. What the hardware sees. Only the low 3 bits arrive: $9\mathrm{mod}8=1$, so $s_2{s}_1{s}_0=001$. It shifts by 1, not 9. Why this step? Truncating a binary number to $k$ bits is the same as taking it $\mathrm{mod}{2}^k=\mathrm{mod}8$.
3. Semantic result. For a logical shift by $\ge n$, every data bit leaves the word → the mathematically correct answer is all zeros. Real ISAs handle this two ways: either mask the amount ($\mathrm{mod}n$, giving the shift-by-1 above) or saturate to 0. Why this step? Every source bit's destination index $\ge n$ is out of range → rule 1 → 0.

Verify (masked model): if input were 0000 0001 and amount masked to 1, output = 0000 0010 = 2. And $9\mathrm{mod}8=1$, $1\times 2^1=2$. ✅ (Saturated model would give 0.)

---

Example 6 — Cell F: rotate right (wrap-around)

Forecast: in a rotate nothing is lost — so where does the top bit land?

1. Binary of $S$. $k={\log }_{2}4=2$. $3=11_2$, so $s_1{s}_0=11$: rotate by 1, then by 2. Why this step? Same decomposition — but now the edge rule is wrap, not zero-fill.
2. Rotate right by 1: $b_j=a_{(j+1)\mathrm{mod}4}$. 1000 → 0100. Why this step? Right rotate pulls from one position higher; the bit leaving the bottom re-enters the top via $\mathrm{mod}4$.
3. Rotate right by 2: apply again. 0100 → 0001. Why this step? $b_j=a_{(j+2)\mathrm{mod}4}$; total wrap displacement $=(1+2)\mathrm{mod}4=3$.

Verify: rotate-right-by-3 of 1000 = rotate-left-by-1 = 0001. Direct check: 1000→0100→0010→0001. ✅ No bits vanished — the hallmark of rotate.

---

Example 7 — Cell G: direction — left vs right on the same input

Forecast: one output should be a bigger number, one smaller — which is which?

1. Left by 2 ($s_1=1$): $b_j=a_{j-2}$. 0001 1000 → 0110 0000. Why this step? Left pulls from a lower index → bits move up → multiply.
2. Value check left: $24\times 2^2=96$. 0110 0000 $=64+32=96$. ✅
3. Right by 2 ($s_1=1$, direction reversed): $b_j=a_{j+2}$, fill top with 0. 0001 1000 → 0000 0110. Why this step? Right pulls from a higher index → bits move down → divide.
4. Value check right: $\lfloor 24/2^2\rfloor =6$. 0000 0110 $=6$. ✅

Verify: left gives $96$, right gives $6$; $96=24\times 4$ and $6=24÷4$. The direction flips the sign of the index displacement. ✅

---

Example 8 — Cell H: real-world word problem (address scaling)

Forecast: why << 3 and not a multiply? (Hint: $8=2^3$.)

1. Why a shift, not a multiplier. Element size $8=2^3$, and multiplying by a power of two is a left shift by that exponent. A shifter costs ${\log }_{2}n$ mux delays; a multiplier costs far more. Why this step? This is the parent's "multiply/divide-by-powers-of-2 every cycle" motivation, concretely.
2. Shift amount $S=3=011_2$ → stages 0 and 1 ON (jumps 1 and 2, sum 3). Why this step? $3$'s binary form selects the sliders.
3. Shift $i=5$ left by 3. $5=$ ...0000 0101 → ...0010 1000. Why this step? Bits at positions 0 and 2 move to positions 3 and 5.

Verify: $5\times 2^3=40$. ...0010 1000 $=32+8=40$. Element 5 lives at byte 40 — matches $5\times 8$. ✅

---

Example 9 — Cell I: exam twist, count the hardware (not the data)

Forecast: which of these scale as $n$, and which as ${\log }_{2}n$?

1. Stages $={\log }_{2}n={\log }_{2}64=6$. Why this step? One optional stage per bit of the shift amount.
2. Control width $=\lceil {\log }_{2}n\rceil =6$ bits (range $0$–$63$). Why this step? $63=111111_2$ needs 6 bits — not 64. This is the classic trap.
3. Total muxes $=n{\log }_{2}n=64\times 6=384$. Why this step? Each of the 6 stages needs $n=64$ muxes, one per output bit.
4. Delay $={\log }_{2}n=6$ mux delays. Why this step? Signal passes through 6 cascaded stages; delay grows logarithmically — the whole point (Logarithmic Delay Structures).

Verify: stages 6, control 6, muxes $384$, delay 6. Consistency: $384/64=6=$ stages = delay. ✅

---

Example 10 — Cell J: exam twist, arithmetic (sign-extending) right shift

Forecast: a logical right shift fills the top with 0. An arithmetic shift is different — guess what fills in.

1. Read the sign bit. Top bit $a_7=1$ → $A$ is negative in two's complement. Its value: $11010000_2=-48$. Why this step? Arithmetic shifts preserve sign, so the sign bit governs the fill rule.
2. Shift the pattern right by 2, but fill the two vacated top bits with copies of $a_7=1$ (not 0). Why this step? Rule 3: arithmetic right shift copies the old sign so the result stays negative — dividing correctly.
3. Apply: 1101 0000 → shift right 2 with sign-fill → 1111 0100. Why this step? Body bits slide down 2; top two positions get 11.

Verify: 1111 0100${}_2=-12$ in two's complement. And $-48/2^2=-12$ (rounding toward $-\infty$). ✅ A logical shift would have given 0011 0100 $=52$ — wrong for signed data.

---

Active Recall

Recall Which matrix cells still use the plain formula

$b_j=\overline{s_i}{a}_j+s_i{a}_{j-2^i}$? All of them — only the out-of-range fill changes (0 for logical, $\mathrm{mod}n$ for rotate, sign-copy for arithmetic). The mux structure is identical.

Recall Why does shift-by-9 on an 8-bit shifter not shift by 9?

The control bus is only $\lceil {\log }_{2}8\rceil =3$ bits; $9$ is truncated to $9\mathrm{mod}8=1$ (masked) or saturated to all-zeros.

Recall 64-bit shifter: muxes and delay?

$n{\log }_{2}n=64\times 6=384$ muxes; delay $=6$ mux delays.

Recall Arithmetic right shift of a negative number fills the top with…?

Copies of the sign bit (1 for negatives), so the value stays negative and the shift equals division by a power of two.

Connections

• Multiplexers — every case is still just 2:1 muxes; only $D_1$ changes.
• Binary Number Representation — decomposing $S$ and the two's-complement value read in Ex 10.
• Shift and Rotate Operations — logical vs rotate vs arithmetic, all drilled above.
• Combinational Circuits — none of these examples needed a clock.
• Logarithmic Delay Structures — the ${\log }_{2}n$ delay counted in Ex 9.
• Floating Point Normalization — the real consumer of fast variable shifts.

Concept Map