# The barrel shifter

*Shifting a word in one combinational step*

A barrel shifter is a combinational circuit that shifts or rotates a word by any amount in a single step, built from a tree of multiplexer stages where stage k shifts by 0 or 2^k under one control bit; a logical shift fills the vacated bits with 0, an arithmetic right shift copies the sign bit, and a rotate wraps the bits around.

Group: Arithmetic
URL: https://digiwleea.wleeaf.dev/learn/shifter/

The [shift register](https://digiwleea.wleeaf.dev/learn/shift-register/) shifts one bit per clock: to move a byte four places you clock it four times. Often you need the shift **now**, in one pass of combinational logic, with the shift amount itself being data (as in `x << y`). That circuit is a **shifter**, and the general form built from [multiplexers](https://digiwleea.wleeaf.dev/learn/mux/) is a **barrel shifter**. It is a standard arithmetic building block, and a standard [ALU](https://digiwleea.wleeaf.dev/learn/alu/) operation, that our ALU does not yet have.

## Shift by a constant is just rewiring

If the shift amount is **fixed** and known when you build the circuit, a shift costs no gates at all: it is pure wiring. To shift `X = X3 X2 X1 X0` left by one, wire `X0` to output bit 1, `X1` to output bit 2, `X2` to output bit 3, and feed a constant `0` into output bit 0. You have just relabelled which wire goes where. And shifting has a meaning in arithmetic: a **left shift by `k` multiplies by `2^k`**, and a **right shift by `k` divides by `2^k`**, exactly as appending a `0` in decimal multiplies by 10. That is exactly what powers shift-and-add multiplication, shown step by step in the [interactive multiplication walkthrough](https://digiwleea.wleeaf.dev/tools/binary-multiplication/).

```
0011 (3) shifted left by 2 = 1100 (12 = 3 × 4)
```

## Three flavors: logical, arithmetic, rotate

Left shifts always bring in `0`s at the bottom. Right shifts are where the flavors differ, and the difference is all about the vacated **top** bits:

- **Logical shift:** fill the vacated bits with `0`. Correct for **unsigned** numbers.
- **Arithmetic shift:** on a right shift, copy the **sign bit** into the vacated top bits (sign-extension). Correct for **signed** [two's-complement](https://digiwleea.wleeaf.dev/learn/twos-complement/) numbers. (Arithmetic left shift is the same as logical left: both fill `0` at the bottom.)
- **Rotate:** no bits fall off; whatever leaves one end wraps around to the other. A rotate loses no information.

Here is why the arithmetic flavor exists. Take `1000`, which is `-8` in 4-bit [two's complement](https://digiwleea.wleeaf.dev/learn/twos-complement/) (the top bit is the sign). Dividing by 2 should give `-4`. An **arithmetic** right shift by 1 copies the sign bit, giving `1100`, which reads as `-4`: correct. A plain **logical** right shift would give `0100`, which is `+4`: nonsense for a signed value. Copying the sign is exactly what keeps a negative number negative as you divide it.

| value | operation | result | reads as |
| --- | --- | --- | --- |
| 1000 | arithmetic right 1 | 1100 | -4 |
| 1000 | logical right 1 | 0100 | +4 |

_1000 is -8 as a signed byte. An arithmetic right shift copies the sign bit and gives -4 (correct half); a logical right shift fills 0 and gives +4 (wrong for a signed value). Same input, same direction, different fill rule._

> **KEY:** A shift is the cheapest arithmetic there is: multiplying or dividing by a power of two is just moving bits, no [adder](https://digiwleea.wleeaf.dev/learn/adder8/) needed. That is why a compiler turns `x * 8` into a left shift by 3, and an unsigned `x / 2` into a right shift by 1. Signed division is close but not identical: an arithmetic right shift rounds toward negative infinity while C's `/` rounds toward zero, so a compiler adds a small correction for negative values. The flavor you pick still encodes whether the value is signed.

## Variable shifts: the barrel shifter

When the shift **amount** is itself a signal (you do not know it until the circuit runs), constant rewiring is not enough: you need to choose, at run time, among all the possible shifts. The trick is to build the shift out of **powers of two**. Any shift from `0` to `N-1` is a sum of `1`, `2`, `4`, ... so lay the shifter out as a stack of stages, one per power of two:

1. **Stage 0** shifts by `0` or `1`, controlled by shift-amount bit `sh0`.
2. **Stage 1** shifts by `0` or `2`, controlled by bit `sh1`.
3. **Stage 2** shifts by `0` or `4`, controlled by bit `sh2`, and so on.
4. Each stage is a **row of 2:1 [multiplexers](https://digiwleea.wleeaf.dev/learn/mux/)**, one per bit: with its control bit `0` the bit passes straight through, with it `1` the bit takes the value from `2^k` positions away.

So an `N`-bit barrel shifter is about `log2(N)` mux layers deep. To shift by `2`, drive the amount `sh1 sh0 = 10` (binary two): stage 0 passes through unchanged, stage 1 shifts by 2. Feed `0011` in and stage 1 produces `1100`, the same `3 -> 12` as before, now selected by data rather than hard-wired. A [4-bit](https://digiwleea.wleeaf.dev/learn/binary/) shifter needs just two stages to reach any shift from 0 to 3.

_Circuit diagram: One stage of a barrel shifter: the shift-left-by-1 layer for a 4-bit value. Four 2:1 muxes share one control S. With S = 0 each Y equals its own X (no shift); with S = 1 each Y takes the bit one position lower (Y1 = X0, Y2 = X1, Y3 = X2) and Y0 is filled with 0. Stack a shift-by-2 stage on top and you can shift by any amount. Open it in the lab and toggle S to watch the whole word slide._

> **TIP:** Contrast the two shift circuits you now know. A [shift register](https://digiwleea.wleeaf.dev/learn/shift-register/) is **sequential**: it moves one position per clock edge and stores the result. A barrel shifter is **combinational**: it delivers the entire shift in one pass, no clock, the output changing as soon as the inputs settle. The register is for streaming data along a wire; the barrel shifter is for computing `x << y` inside an [ALU](https://digiwleea.wleeaf.dev/learn/alu/).

> **WARN:** **Common mistakes.** Using a **logical** right shift on a signed value (a negative number turns large and positive); signed division must sign-extend with an arithmetic shift. Confusing **rotate** with **shift** (a rotate wraps and loses no bits; a shift drops bits off the end). Assuming a variable shifter must be **clocked**, when a barrel shifter is purely combinational and produces the shift in one pass. And forgetting that arithmetic **left** shift fills `0` just like a logical left shift (the sign trick is a right-shift thing), so a left shift can still overflow the sign bit.

**Q (Try it):** Take the 4-bit value `0110` (6). Compute (a) a logical left shift by 1, (b) an arithmetic right shift by 2 treating it as a signed number, and (c) a rotate right by 1.

**A:** (a) Logical left by 1: bring in a `0` at the bottom, `0110 -> 1100` = `12` (that is `6 * 2`). (b) `0110` is `+6` (sign bit `0`); arithmetic right by 2 copies the sign `0` into the top, `0110 -> 0001` = `1` (that is floor(6 / 4); an arithmetic right shift rounds toward negative infinity). (c) Rotate right by 1: the low bit `0` wraps to the top, `0110 -> 0011` = `3`; no bit is lost.

> **KEY:** Shifting completes the arithmetic toolkit: with add, subtract, multiply, and shift you can build the multiply-and-divide-by-powers-of-two paths a real datapath leans on. A full [ALU](https://digiwleea.wleeaf.dev/learn/alu/) usually lists a shift among its selectable operations right next to add and AND; the barrel shifter is the block that supplies it. Next, division is the harder inverse, the same shift idea run as shift-and-subtract.

### FAQ

**Q:** What is a barrel shifter?

**A:** A barrel shifter is a combinational circuit that shifts or rotates a word by any amount in a single pass of logic, built from a tree of [multiplexer](https://digiwleea.wleeaf.dev/learn/mux/) stages where stage `k` shifts by `0` or `2^k` under one bit of the shift amount. An `N`-bit barrel shifter is about `log2(N)` mux layers deep, and unlike a [shift register](https://digiwleea.wleeaf.dev/learn/shift-register/) it needs no clock.

**Q:** What is the difference between a logical and an arithmetic shift?

**A:** They differ only on a right shift and only in what fills the vacated top bits. A **logical** right shift fills `0`, which correctly divides an **unsigned** number. An **arithmetic** right shift copies the **sign bit** into the vacated bits, which divides a **signed** [two's-complement](https://digiwleea.wleeaf.dev/learn/twos-complement/) number while keeping its sign. Using a logical shift on a negative value turns it large and positive.

**Q:** What is the difference between a shift register and a barrel shifter?

**A:** A [shift register](https://digiwleea.wleeaf.dev/learn/shift-register/) is **sequential**: it moves the stored bits one position per [clock](https://digiwleea.wleeaf.dev/learn/clock/) edge, so an N-position shift takes N clocks. A barrel shifter is **combinational**: it produces the whole shift by any amount in one pass with no clock, using a tree of muxes. The register streams data; the shifter computes a shift.

**Q:** Why is shifting the same as multiplying or dividing by a power of two?

**A:** Shifting a binary number left by `k` moves every bit into a higher place and brings in `0`s, which multiplies it by `2^k`, exactly as appending a `0` multiplies a decimal number by 10. Shifting right by `k` divides by `2^k`. This needs no [adder](https://digiwleea.wleeaf.dev/learn/adder8/), only rewiring, so `x * 8` becomes a left shift by 3.