Barrel shifters: Question bank — Hardware deep dive

This page assumes you have read the parent Barrel Shifters note. Every term used here (stage, 2:1 mux, ==shift amount $S$ , power-of-two decomposition==) is defined there — jump back if any feels unfamiliar before you continue.

True or false — justify

A barrel shifter needs

n

stages to shift an

n

-bit word by up to

n - 1

places.

False. It needs only

lo g_{2} n

stages, because each stage shifts by a distinct power of two (

1, 2, 4, \dots

) and any amount

0

n - 1

is a sum of those powers — the binary digits of

S

pick which stages turn on.

The shift-amount control

S

must be the same width as the data (

n

bits).

False.

S

only ranges from

0

n - 1

, so it needs

⌈ lo g_{2} n ⌉

bits. For

n = 16

that is 4 control bits, not 16 — one control bit per stage, not per data bit.

Shift stages and rotate stages use completely different circuits.

False. Both are rows of 2:1 muxes with identical selection logic; only the second data input differs — a shift feeds a constant

0

into vacated positions, a rotate feeds the wrapped-around bit

a_{(j - 2^{i}) mod n}

For pure shifts, reordering the stages (e.g. doing the shift-by-4 stage before the shift-by-1 stage) changes the final data output.

False. Displacements simply add, so shift-by-4 then shift-by-1 equals shift-by-1 then shift-by-4 — the stages commute. (Wiring inside each stage still must be correct; only their order is free.)

A barrel shifter is a sequential (clocked) circuit because it "does many shifts".

False. It is purely combinational — no clock, no state. The "many shifts" happen simultaneously through cascaded mux layers within a single cycle; the output is a pure function of the inputs.

Doubling the data width

n

roughly doubles the propagation delay.

False. Delay is

lo g_{2} n

mux-delays, so doubling

n

adds only one extra stage (one mux delay). This logarithmic growth is the whole point — see Logarithmic Delay Structures.

The total mux count

n lo g_{2} n

means each mux handles

lo g_{2} n

bits.

False. There are

lo g_{2} n

stages, each with

n

muxes (one per output bit), giving

n lo g_{2} n

simple 2:1 muxes — each still handles just one bit. It is the product of "bits per stage" and "number of stages".

If a stage's control bit

s_{i}

is 0, that stage's muxes do nothing at all and can be removed.

False. When

s_{i} = 0

the muxes still actively select the pass-through input

a_{j}

; the data physically flows through them. They cannot be removed because on a different cycle

s_{i}

may be 1.

Spot the error

"To shift a 32-bit word we need 32 stages of muxes." — find the mistake.

Wrong count: a 32-bit shifter needs

lo g_{2} 32 = 5

stages (for shifts of 1,2,4,8,16), not 32. The confusion comes from imagining a 1-bit-at-a-time shifter; powers of two collapse the layer count to logarithmic.

"The per-bit equation

b_{j} = \overline{s_{i}} a_{j} + s_{i} a_{j - 2^{i}}

works for every

j

with no special case." — find the mistake.

It ignores the boundary: when

j - 2^{i} < 0

the index

a_{j - 2^{i}}

doesn't exist. For a logical shift that term is forced to

0

(fill with zero); for a rotate the index is taken

mod n

. The bare equation only holds where the index is valid.

"A rotate-left stage and a shift-left stage differ in their select signal." — find the mistake.

They share the same select signal

s_{i}

. The real difference is in the second data input

D_{1}

a_{j - 2^{i}}

(with 0-fill) for a shift versus

a_{(j - 2^{i}) mod n}

(wrap) for a rotate.

"Shifting left by 13 requires stages for 1, 3, 4, and 5 because

1 + 3 + 4 + 5 = 13

." — find the mistake.

Stages only exist for powers of two, not arbitrary numbers.

13 = 110 1_{2} = 8 + 4 + 1

, so the active stages are the 8-, 4-, and 1-stages. There is no "3-stage" or "5-stage".

"Because

S

can be 0, we need an extra 'no-shift' stage." — find the mistake.

No extra stage is needed.

S = 0

means every control bit is 0, so all stages pass through unchanged — the zero shift is already covered by the existing stages, not a special one.

"Each stage is a big

n

-to-1 multiplexer." — find the mistake.

Each output bit only chooses between two possibilities (shifted vs not), so each stage is a row of

n

tiny 2-to-1 muxes, not one giant

n

-to-1 mux. An

n

-to-1 mux would be far more expensive and defeats the elegant power-of-two design.

Why questions

Why do we decompose

S

into powers of two rather than, say, tens or arbitrary chunks?

Because hardware selection is naturally binary: one control bit is either 0 or 1, so it can only turn a single fixed shift on or off. Powers of two are exactly the values a binary positional system offers per bit, letting

lo g_{2} n

bits address every amount — see Binary Number Representation.

Why is a barrel shifter faster than a naïve 1-bit shifter for a shift of 7?

The naïve shifter iterates 7 clock cycles (one bit each). The barrel shifter routes all displacements through

lo g_{2} n

mux layers in one cycle, so its delay is a fixed logarithmic constant regardless of the shift amount.

Why must the shift amount be known at the inputs rather than computed during the shift?

Because the circuit is combinational — it has no internal steps or memory. All control bits

s_{i}

must be present so the muxes can settle to their final selection; there is no notion of "computing as it goes".

Why does floating-point normalization care about single-cycle shifting?

Normalization must shift the mantissa by however many leading zeros exist, every arithmetic operation. A multi-cycle shifter would stall the pipeline on every float op; the barrel shifter does it in one cycle — see Floating Point Normalization.

Why does the mux count grow as

n lo g_{2} n

rather than

n^{2}

n

Each of the

lo g_{2} n

stages needs one mux per output bit (

n

muxes), and stages are cascaded not cross-connected, so the total is the product

n \times lo g_{2} n

— linear in bits, logarithmic in stages.

Edge cases

What does the barrel shifter output when

S = 0

The unchanged input. Every control bit is 0, so every stage selects its pass-through input

b_{j} = a_{j}

— the data flows straight through untouched.

For an

n

-bit rotate, what happens when

S = n

(a full rotation)?

With

⌈ lo g_{2} n ⌉

control bits,

S

maxes out at

n - 1

, so

S = n

usually isn't representable — but conceptually a rotate by

n

returns the original word, since

(j - n) mod n = j

. A full rotation is the identity.

What is the output of a logical left shift by

n - 1

on an

n

-bit word whose only set bit is bit 0?

Only the top bit survives: the single 1 moves to position

n - 1

and every other position is 0-filled. Shifting it further (impossible here) would push it off and yield all zeros.

For a rotate, is there ever a situation where a bit is lost?

No. A rotate never discards bits — each bit that would fall off one end wraps to the other via the

mod n

index, so the output is always a permutation of the input bits (same number of 1s).

What happens to a logical shift when every stage is turned on for an 8-bit word (shift by

1 + 2 + 4 = 7

) and the input is 0000\,0001?

The lone 1 moves from bit 0 to bit 7, giving 1000\,0000; had we shifted by 8 or more (not possible with 3 stages) the bit would be lost to 0-fill entirely.

If two stages accidentally both shift by the same power of two (a wiring bug), what breaks?

The reachable shift amounts change: you can no longer produce that missing power alone, and some amounts become unreachable while others double up. The clean "sum of distinct powers = any amount" guarantee is destroyed.

Connections

Multiplexers — every trap here ultimately rests on what a 2:1 mux does.
Binary Number Representation — the "powers of two" answers all trace back to positional binary.
Combinational Circuits — the "no clock" edge cases.
Shift and Rotate Operations — the shift-vs-rotate distinctions.
Logarithmic Delay Structures — the delay/count reasoning.
Floating Point Normalization — the real-world "why fast" motivation.