Foundations — Barrel shifters

Before we can even read the parent note, we must earn every symbol it throws at us: bits, indices, powers of two, binary, ${\log }_{2}n$, the mux equation, and the little $\mathrm{mod}$ sign. This page builds each one from the ground, in an order where nothing appears before it is defined.

1. A bit, and a word of bits

Picture a row of light switches. Each switch is either OFF ($0$) or ON ($1$). Put $n$ of them in a line and you have a word — the thing a shifter shifts.

Why does the topic need this? A barrel shifter takes a word in and gives a word out. If we don't nail down "what is a word," every later sentence is unreadable.

2. The index $j$ and the position of a bit

Each switch in the row needs a name so we can talk about "the third one." That name is its index.

Why count from the right and start at $0$? Look at the next section: the value of a bit depends on $2^j$, and starting at $0$ makes the rightmost bit worth $2^0=1$. It lines up the picture with the arithmetic.

3. Powers of two, $2^i$

The whole trick of a barrel shifter is powers of two, so let's make sure that notation is solid.

Picture doubling: start with 1 domino, double to 2, double to 4, double to 8. Each step is $\times 2$; after $i$ steps you have $2^i$.

4. Binary — writing numbers as sums of powers of two

Take $13$. Ask: which powers of two add up to $13$? $13=8+4+1=2^3+2^2+2^0$ Include $2^3,2^2,2^0$; skip $2^1$. Reading the switches from $2^3$ down to $2^0$: $1101$. So $13=1101_2$ (the small $2$ means "read this as binary").

The tall $\sum$ ("sigma") is just shorthand for "add all of these up." The label $i=0$ underneath is the starting index; the $k-1$ on top is the last. This is why the parent can say "shift-by-13 = shift-by-8 + shift-by-4 + shift-by-1" — that sentence IS the binary expansion of $13$.

See Binary Number Representation for the full rules of this number system.

5. The logarithm ${\log }_{2}n$ — how many switches do we need?

We have powers of two ($1,2,4,8,\dots$) as our building blocks. Question: to build any amount from $0$ up to $n-1$, how many of these blocks (switches) do we need?

Picture climbing the doubling ladder from the previous figure: $1\to 2\to 4\to 8\to 16$ is 4 rungs, so ${\log }_{2}16=4$.

6. The multiplexer — the single Lego brick

Every stage is built from one repeated part: the multiplexer. Full detail lives in Multiplexers; here is the minimum you need.

Now three tiny logic symbols so the mux equation reads cleanly:

Put them together and the mux is a one-line formula: $\text{out}=\overline{sel}\cdot D_0+sel\cdot D_1$ Read it: "if $sel=0$ then $\overline{sel}=1$ so the first term is $D_0$ and the second term is $0$ — output is $D_0$. If $sel=1$, the second term wins — output is $D_1$." That is a mux, derived, not assumed. Every per-bit stage equation in the parent note is just this formula with $D_0=a_j$ and $D_1=$ the shifted bit.

7. Shift versus rotate, and the $\mathrm{mod}$ sign

When bits slide sideways, some fall off the edge. What replaces them?

To say "wrap around" in math we need one more symbol:

See the Hinglish companion if you'd like these ideas restated in mixed Hindi-English.

8. How the pieces feed the topic

Every arrow says "you must understand the tail before the head makes sense." Follow them left-to-right and the parent note reads like plain English.

Equipment checklist

Cover the right side and answer aloud. If any stumps you, re-read its section above.

Connections

• Multiplexers — the 2:1 mux brick every stage is made of.
• Binary Number Representation — the sum-of-powers-of-two decomposition.
• Combinational Circuits — the AND/OR/NOT gate world these live in.
• Shift and Rotate Operations — the two edge behaviours defined here.
• Logarithmic Delay Structures — why ${\log }_{2}n$ growth is the whole point.
• Floating Point Normalization — a real consumer of fast shifting.