Shifters and Rotators

Shift bits in zeros or the sign, rotate them around, and build a barrel shifter in log2 N stages.

You Will Be Able To

  • Tell logical, arithmetic and rotate shifts apart.
  • Explain why a shift by a constant costs no gates.
  • Build a barrel shifter from log2 N stages of 2:1 muxes.
  • Describe a funnel shifter and the shifts it covers.
Lesson
G4.9
Time
25 min
Runs on
Your browser
Check
5 questions

A filter divides a signed sample by 4 with a right shift. The sample arrives on a plain logic port. For −8 the filter outputs 62, and the audio clicks on every negative sample.

Dividing by 4 with a ShiftTwo samples. raw is the byte on the unsigned port; s is the same bits declared signed.
01sample-8-28raw >>> 26257signed >>> 2-2-762, not −2
Scroll horizontally ↔
  1. Cycle 0

    −8 is f8. On an unsigned value >>> shifts in zeros, so the result is 3e = 62, the same as >>.

  2. Cycle 1

    Declared signed, the same bits shift in copies of the sign bit: −28 / 4 = −7.

Measured on the simulator.

Logical, Arithmetic and Rotate

A logical shift moves the bits and fills the empty places with 0. An arithmetic right shift fills them with copies of the sign bit, so a negative number stays negative. A rotate puts the bits that fall off one end back in at the other.

Operation on x = 1011_0010Written asResult
logical left by 2x << 211001000
logical right by 2x >> 200101100
arithmetic right by 2 (x signed)xs >>> 211101100
rotate left by 2{x[5:0], x[7:6]}11001010
rotate right by 2{x[1:0], x[7:2]}10101100

Measured on the simulator. A left shift by n multiplies by 2^n; a right shift divides, rounding down.

A Constant Shift Is Only Wires

Shifting by a fixed amount moves each bit to a fixed place. No decision is made, so no gate is needed. Bit i of x << 3 is wire i − 3 of x, and the low three bits are tied to 0.

On this site, x << 3 on a byte synthesized to 0 cells. A multiply by 8 is free when it is written as a shift, and the synthesizer finds the shift on its own.

A shift by a variable amount is different: every output bit must choose among several inputs. That choice is a mux.

The Barrel Shifter: One Stage per Bit of the Amount

Write the shift amount n in binary. Shift by 1 if bit 0 is set. Then shift by 2 if bit 1 is set, and by 4 if bit 2 is set. The shifts add up to n. Each stage is a row of 2:1 muxes that either passes the word or shifts it by its fixed amount.

Rotate Left by 5 = 1 + 4, in Three StagesEach stage is a row of 2:1 muxes. Its select is one bit of n. The token follows the bit that starts at position 1.
  • I/O
  • Datapath
  • Data
  • Control
CallValueReturnWaiting
Rotate left by 5 = 1 + 4, in three stagesEach stage is a row of 2:1 muxes. Its select is one bit of n. The token follows the bit that starts at position 1. io x 10000110 datapath Stage 1 by 1 if n[0] datapath Stage 2 by 2 if n[1] datapath Stage 4 by 4 if n[2] io n = 101 shift amount io y 11010000 word000011010000110111010000n[0] = 1
  1. io x10000110
    • word → Stage 1
  2. datapath Stage 1by 1 if n[0]
    • 00001101 → Stage 2
  3. io n = 101shift amount
    • n[0] = 1 → Stage 1
  4. datapath Stage 2by 2 if n[1]
    • 00001101 → Stage 4
  5. datapath Stage 4by 4 if n[2]
    • 11010000 → y
  6. io y11010000
  1. Stage 1: n[0] = 1

    The word rotates by one place. The bit from position 1 moves to position 2.

    Follow the calls, values and waits
    1. data now at 2: Stage 1 → Stage 2
  2. Stage 2: n[1] = 0

    This stage passes the word unchanged.

    Follow the calls, values and waits
    1. data now at 2: Stage 2 → Stage 4
  3. Stage 4: n[2] = 1

    The word rotates by four. The bit moves from 2 to 6. In all it moved 5 places.

    Follow the calls, values and waits
    1. data now at 6: Stage 4 → y
Read the diagram as text
  • x: 10000110
  • Stage 1: by 1 if n[0]
  • Stage 2: by 2 if n[1]
  • Stage 4: by 4 if n[2]
  • n = 101: shift amount
  • y: 11010000
  • x → Stage 1: word
  • Stage 1 → Stage 2: 00001101
  • Stage 2 → Stage 4: 00001101
  • Stage 4 → y: 11010000
  • n = 101 → Stage 1: n[0] = 1

An N-bit barrel shifter has log2 N stages of N muxes each: 3 stages of 8 for a byte.

The lab below is this rotator. It synthesized to 24 mux cells in 3 levels. The same rotate written as (x << n) | (x >> (8 − n)) came out at 74 cells and 7 levels. Here the stage structure you write survives synthesis.

The Funnel Shifter

A funnel shifter takes a 2N-bit word {hi, lo}, shifts it right by n and keeps the low N bits. What goes into hi decides the operation.

hiloResult: low N bits of {hi, lo} >> n
all 0xlogical right shift of x
N copies of x's sign bitxarithmetic right shift of x
xxrotate right of x
the next wordxa window across two words, as in a byte stream

One right shifter of 2N bits covers every right shift and rotate.

Asked in interviews
  1. What is the difference between >> and >>>?

    >> always fills with zeros. >>> fills with the sign bit, but only when the operand is signed; on an unsigned value it behaves like >>.

  2. How do you build a barrel shifter?

    With log2 N stages of 2:1 muxes. Stage k shifts by 2^k places when bit k of the amount is 1, and passes the word otherwise.

  3. Does an arithmetic shift right divide by 2^n?

    It rounds toward minus infinity, so −7 >>> 1 is −4. The / operator rounds toward zero and gives −3.

Try It

The bench rotates 10000110 by every amount and compares with a rotate made from two shifts. All eight agree.

Swap the amounts of the 2-place and the 4-place stages and run. Four rotations go wrong. Which four survive, and why?

Make it a logical left shift: replace the bits that wrap around with zeros, for example {x[6:0], 1'b0} in the first stage.

Press Synthesize and compare the cells with the operator form of the same rotate.

RTLIcarus Verilog · in your browser · Lint: Verilator service · Synthesize: Yosys service
Edit the design, then Run, Lint or Synthesize
Expected: n=0 y=10000110 n=1 y=00001101 n=2 y=00011010 n=3 y=00110100 n=4 y=01101000 n=5 y=11010000 n=6 y=10100001 n=7 y=01000011 0 of 8 rotations wrong

Original design · 24 cells · 0 flip-flops · 0 latches · 3 logic levels. Synthesis uses Yosys; counts depend on the toolchain.

Read included file: tb.sv
// tb.sv: every rotate amount for one word, checked against a rotate built from two shifts (read-only).
module tb;
  logic [7:0] x, y, want;
  logic [2:0] n;
  int wrong = 0;
  rotl8 dut (.x(x), .n(n), .y(y));
  initial begin
    x = 8'b1000_0110;
    for (int k = 0; k < 8; k++) begin
      n = k[2:0];
      #1;
      want = (x << n) | (x >> (8 - n));
      if (y !== want) wrong++;
      $display("n=%0d y=%b", n, y);
    end
    $display("%0d of 8 rotations wrong", wrong);
  end
endmodule

Check Yourself

Spot the bugEach option is the body of an always_comb block of an 8-bit right rotate. The bench tries 64 seeded words and amounts. Which body fails?
ConceptWhat does x >>> 2 give for an unsigned 8-bit x = 1000_0000?
ConceptWhich shift of a signed byte gives the result −4 for the input −7?
ConceptHow many gates does a 16-bit shift left by a constant 5 need?
Predict the outputPredict the exact line: a byte rotated right by 3 with a concatenation.
module tb;
  logic [7:0] x = 8'b1100_0101;
  initial $display("%b", {x[2:0], x[7:3]});
endmodule

Common Mistakes

Wrong Use >>> on an unsigned value and expect the sign to be kept.

>>> fills with the sign bit only when the operand is signed. On a plain logic it fills with zeros, so −8 >>> 2 gives 62.

Fix Declare the value signed, or write $signed(x) >>> n.

Before
logic [7:0] raw;
assign q = raw >>> 2;
After
logic [7:0] raw;
assign q = $signed(raw) >>> 2;

Wrong Apply the stages of a barrel shifter with the wrong amounts.

Stage k must move by 2^k places when bit k of the amount is 1. Stages of 1, 2 and 3 cannot make a shift of 7, and make 3 in two ways.

Fix Use 1, 2, 4, 8, ... places, one stage per bit of the shift amount.

Wrong Use a shift where a rotate is needed.

A shift drops the bits that leave the word and fills with zeros. A rotate puts them back at the other end.

Fix Rotate with a concatenation of the two parts, or with a funnel shifter fed the same word twice.

Wrong Expect an arithmetic right shift to divide like the / operator.

The shift rounds toward minus infinity: −7 >>> 1 is −4. Division rounds toward zero and gives −3.

Fix For a division that rounds toward zero, add 2^n − 1 to a negative value before the shift.

Remember

  • Logical shifts fill with 0; an arithmetic right shift fills with the sign; a rotate wraps around.
  • >>> keeps the sign only on a signed operand.
  • A shift by a constant is wiring and costs no gates.
  • A barrel shifter has log2 N stages of 2:1 muxes, shifting by 1, 2, 4, ... places.
  • A funnel shifter of 2N bits covers logical, arithmetic and rotate right shifts.

Practice

Report a problem with this page