Exercises — Barrel shifters

WHAT we compute: the stage count $k=\lceil {\log }_{2}n\rceil$. For $n=8$ (a power of two): $k={\log }_{2}8=3$ stages, shifting by $2^0=1$, $2^1=2$, $2^2=4$. Each stage is a row of $n$ two-to-one (2:1) multiplexers — one mux per output bit. See Multiplexers. Answer: 3 stages, each a row of 8 2:1 muxes.

The shift amount ranges from $0$ to $n-1=31$. The number of bits needed to count up to 31 is $\lceil {\log }_{2}32\rceil =5$. Answer: 5 bits. (Do not confuse this with the data width of 32; see the mistake below.)

Step 1 — write $S$ in binary. $22=16+4+2=10110_2$, so $s_4{s}_3{s}_2{s}_1{s}_0=10110$. Step 2 — read off the ON stages (the 1-bits):

• $s_1=1\Rightarrow$ shift by $2^1=2$
• $s_2=1\Rightarrow$ shift by $2^2=4$
• $s_4=1\Rightarrow$ shift by $2^4=16$ Step 3 — check the sum: $2+4+16=22$. ✅ Answer: stages for 2, 4, and 16 are ON; stages for 1 and 8 pass through.

A single set bit at position $0$, shifted left by $S$, lands at position $S$. So it lands at position $22$. The output value is $2^{22}=4194304$. WHAT IT LOOKS LIKE: figure below — the lone bit slides through three ON stages (2, then 4, then 16), climbing $2\to 6\to 22$ in position.

With $s_2=1$: $\overline{s_2}=0$, so the first term drops and $b_5=a_{5-4}=a_1=1$. Answer: ==$b_5=1$==. The output at position 5 picked up whatever was 4 positions lower (position 1), exactly what "shift left by 4" means.

For $n=64$: ${\log }_{2}64=6$.

• Total muxes $=n{\log }_{2}n=64\times 6=384$.
• Delay $={\log }_{2}n=6$ mux-delays.

Double to $n=128$ (${\log }_{2}128=7$):

• Muxes $=128\times 7=896$.
• Delay $=7$ mux-delays.

The insight: doubling the width more than doubles the muxes ($384\to 896$, a $\times 2.33$ jump — because both $n$ and ${\log }_{2}n$ grew) but the delay rose by only one mux-delay. That gentle delay growth is the whole selling point — see Logarithmic Delay Structures.

False. Take a single input bit at position $j$.

• Order A (by 2, then by 8): $j\to j+2\to (j+2)+8=j+10$.
• Order B (by 8, then by 2): $j\to j+8\to (j+8)+2=j+10$. Both land at $j+10$ because addition of the displacements commutes ($2+8=8+2$). Every set bit moves by the same total, so the words are identical. Answer: order does not change the final data (for pure shifts/rotates).

$S=3=11_2$, so $s_1{s}_0=11$: rotate right by $2^0=1$, then by $2^1=2$.

• Stage 0 (rotate right by 1): each output bit pulls from one position higher, wrapping mod 4. $1000\to 0100$. (The top bit wrapped down.)
• Stage 1 (rotate right by 2): pull from 2 higher, mod 4. $0100\to 0001$. Direct check: rotating 1000 right by 3 slides the single 1 from position 3 to position $3-3=0$: 0001. ✅ Answer: ==$0001$==.

$n=8\Rightarrow k=3$ stages: shift by 1 ($i=0$), 2 ($i=1$), 4 ($i=2$). Per-bit left-shift equation is $b_j=\overline{s_i}{a}_j+s_i{a}_{j-2^i}$, with $a_{<0}=0$ (logical fill). For $j=7$:

• Stage 0 ($2^0=1$): $b_7=\overline{s_0}{a}_7+s_0{a}_6$
• Stage 1 ($2^1=2$): $b_7=\overline{s_1}{a}_7+s_1{a}_5$
• Stage 2 ($2^2=4$): $b_7=\overline{s_2}{a}_7+s_2{a}_3$ Cascade the three (output of one feeds the next). Total muxes $=8\times 3=24$; delay $=3$ mux-delays. See figure for the three-layer wiring of one bit column.

Normalization happens every floating-point add/subtract, and the required shift can be anywhere from $0$ up to $23$ positions depending on cancellation. A 1-bit shifter would take up to 23 clock cycles, stalling the pipeline every time. A barrel shifter does any amount in one pass of combinational logic, so normalization costs a fixed, small delay independent of the shift size. The width $24$ is not a power of two, so we use $k=\lceil {\log }_{2}24\rceil =5$ stages (shift by $1,2,4,8,16$) on a 24-bit-wide datapath — the shifter matches the actual mantissa width, we do not widen the data to 32. The five stages still cover every amount $0\dots 23$; the top ($16$) stage is simply left off for amounts below 16. Worst-case delay $=5$ mux-delays. See Floating Point Normalization.

Design idea: a right shift by $S$ on an $n$-bit word equals a left shift by $n-S$ followed by masking — but the clean textbook trick is: bit-reverse the input, do a left shift, bit-reverse the output. Reversal is free wiring (no gates). So:

1. Optionally reverse input (controlled by $d$) — one row of $n$ 2:1 muxes selecting straight vs reversed wiring.
2. One $k$-stage left barrel shifter: $n{\log }_{2}n$ muxes.
3. Optionally reverse output (controlled by $d$) — another row of $n$ muxes.

Cost for $n=16$ (${\log }_{2}16=4$):

• Core: $16\times 4=64$ muxes.
• Two reversal rows: $2\times 16=32$ muxes.
• Total $=96$ muxes.

Versus two separate shifters: two independent barrel shifters cost $2\times 64=128$ muxes plus an output selector row of $16$ = $144$. The reverse-shift-reverse design (96) is cheaper and reuses the single expensive core. ✅

Proof. The shift amount ranges $0$ to $n-1$, a $\lceil {\log }_{2}n\rceil$-bit number, so we need one stage per bit $\Rightarrow \lceil {\log }_{2}n\rceil$ stages. Each stage produces all $n$ output bits, and each output bit is one 2:1 mux $\Rightarrow n$ muxes per stage. Multiply: $\text{stages}\times \text{muxes/stage}=\lceil {\log }_{2}n\rceil \cdot n=n\lceil {\log }_{2}n\rceil$. ∎ When $n$ is a power of two the ceiling vanishes and this is the familiar $n{\log }_{2}n$. For $n=1024=2^{10}$: ${\log }_{2}1024=10$, so $1024\times 10=10240$ muxes; delay $=10$ mux-delays.

$n=256$. Stages $={\log }_{2}256=8$; muxes $=256\times 8=2048$; delay $=8$ mux-delays; control width $=8$ bits.

$45=101101_2$, so stages for $32,8,4,1$ (sum $=45$).