A shift by a variable amount

Shifting by a constant is only wiring. Shifting by a variable amount needs a multiplexer network.

A barrel shifter has one stage per bit of the shift count. Stage k passes the data through or shifts it by 2ᵏ positions, selected by bit k of the count.

Any shift from 0 to N−1 is a sum of stage shifts, so log₂ N stages are enough.

N may be 1 (a single-bit shifter): the shift-amount width is guarded as localparam int SW = (N > 1) ? $clog2(N) : 1; because $clog2(1) is 0, which would give a [-1:0] amount.

Watch amt pick the stages: s1 always equals s0 because amt[1] stays 0. The diagram shows hex values.

• Slot 1: amt is 0, so every stage passes the value through and y is 01.

• Slot 2: amt is 1, so only stage 0 shifts and s0, s1 and y are 02.

• Slot 3: amt is 4, so only stage 2 shifts and y is 10.

• Slot 4: amt is 5, so stages 0 and 2 shift and y is 20.

• Slot 5: new data 03 shifted by 5 gives s0 of 06 and y of 60.

Shift modes

For an arithmetic right shift, each stage opens up 2ᵏ top bits. Each opened bit is a copy of the original sign bit. So one precomputed fill works for every stage.

Two modes are missing on purpose.

• No arithmetic-left mode. Left shifts always fill with 0, so logical and arithmetic left match.

• No rotate-right mode. Rotate-right by k equals rotate-left by (N − k), so a left-only rotator is enough.

Cost

• Delay: log₂ N mux stages, not N. A 32-bit shifter has 5 stages.

• Area: N·log₂ N 2:1 multiplexers. Doubling the width a little more than doubles the cost.

• A shifter that supports only left shifts and uses a bit-reversal trick for right shifts can share the same stages, at the cost of two reversal layers.

Common mistakes

A common interview task is implementing a barrel shifter.

• Stage per count bit: stage k shifts by 2ᵏ when amt[k] is set.

• Fill decides the mode: 0 for logical, sign bit for arithmetic right, wraparound for rotate.

• Cost is log₂ N stages, so a 32-bit shifter needs 5.

Testbench

The barrel shifter plus a testbench that checks every mode against the language operators.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

module barrel #(parameter int N = 8) (   // N must be at least 1
  input  logic [N-1:0]         d,
  input  logic [(N > 1 ? $clog2(N) : 1)-1:0] amt,
  input  logic [1:0]           mode,     // 0: logical left, 1: logical right, 2: arithmetic right, 3: rotate left
  output logic [N-1:0]         y
);
  // N = 1 guard ($clog2(1) is 0, so [$clog2(N)-1:0] would be [-1:0]).
  localparam int SW = (N > 1) ? $clog2(N) : 1;
  logic [N-1:0] s [SW+1];
  logic         fill;

  always_comb begin
    fill = (mode == 2'd2) ? d[N-1] : 1'b0;     // arithmetic right fills with the sign bit
    s[0] = d;
    for (int k = 0; k < SW; k++) begin
      if (amt[k]) begin
        case (mode)
          2'd0:    s[k+1] = s[k] << (1 << k);
          2'd1:    s[k+1] = s[k] >> (1 << k);
          2'd2:    s[k+1] = (s[k] >> (1 << k)) | ({N{fill}} << (N - (1 << k)));
          default: s[k+1] = (s[k] << (1 << k)) | (s[k] >> (N - (1 << k)));
        endcase
      end else begin
        s[k+1] = s[k];
      end
    end
    y = s[SW];
  end
endmodule

Related topics

• Shift and arithmetic intent

• Mini project: a leading-zero counter and normaliser