Shifts, Rotates, Barrel Shifters and Streaming

Predict what each shift operator puts in the empty bits. Know what a shift, a rotate and a streaming operator cost in gates.

You Will Be Able To

  • Predict when >>> fills with the sign bit and when it fills with zeros.
  • Explain why a constant shift is free and a variable shift is a barrel shifter.
  • Write a variable rotate from one shift of a double-width vector.
  • Choose a streaming operator to reverse the bits or the bytes of a bus.
Lesson
R10.3
Time
30 min
Runs on
Your browser
Check
5 questions

A volume control divided each audio sample by 4. Quiet passages were fine. Every negative sample came out as a large positive one, and the speaker clicked.

The operand is declared unsigned

input  logic [7:0] sample;   // -128 to 127
...
assign y = sample >>> sh;

Icarus 12 for a sample of -64 and sh = 2: y= 48 (00110000). Two zeros came in at the top.

The operand is signed

input  logic [7:0] sample;   // -128 to 127
...
assign y = $signed(sample) >>> sh;

Icarus 12: y= -16 (11110000). Two copies of the sign bit came in. Lint is silent on both versions.

Three Shifts and What Fills the Gap

A shift moves every bit of a vector left or right. Bits that leave the vector are lost. The operator decides what enters at the other end.

ExpressionOperand 1100_0101ResultWhat came in
u << 2unsigned0001_0100zeros at the bottom
u >> 2unsigned0011_0001zeros at the top
u >>> 2unsigned0011_0001zeros: the operand is not signed
s >> 2signed0011_0001zeros: >> never looks at the sign
s >>> 2signed1111_0001copies of the sign bit
s <<< 2signed0001_0100zeros: the same as <<
u >> 9, u << 8unsigned0000_0000every bit left the vector
s >>> 9signed1111_1111only sign bits are left

Icarus 12 and Verilator 5.052 print the same eight rows.

>>> is the arithmetic right shift. It keeps the sign only when the expression it shifts is signed. Lesson R1.4 gives the rule: an expression is signed only if every operand is.

Assigned to an 8-bit y, with s = 1100_0101ResultWhy
y = s >>> 2;1111_0001the operand is signed
y = $signed(u) >>> 2;1111_0001the cast makes it signed
y = s[7:0] >>> 2;0011_0001a part-select is unsigned
y = (s >>> 2) + 8'd0;0011_00018'd0 is unsigned, so the whole expression is
y = (s >>> 2) + 0;1111_0001a plain 0 is signed
y = pick ? s >>> 2 : u;0011_0001the other arm is unsigned

Measured on both simulators. One unsigned operand anywhere in the expression turns the shift into a zero fill.

A Constant Shift Is Wiring

When the amount is a constant, each output bit is one fixed input bit or a 0. Synthesis connects wires and builds nothing.

Design (8 bits)CellsLevels
a << 3, a >> 1 and a signed sa >>> 2 together00
{a[4:0], 3'b000}, the same left shift as a concatenation00

Measured on this flow. Multiplying or dividing by a constant power of two is free.

The width still matters. A shift is done at the width of its left operand and its context. With n at 9, 8'd1 << n printed 0 in $display, where nothing widens it. Assigned to a 16-bit mask it gave 512. A plain 1 << n is 32 bits wide and printed 512.

A Variable Shift Is a Barrel Shifter

When the amount is a signal, every output bit can come from several input bits. The circuit is a barrel shifter: one row of muxes for each bit of the amount.

An 8-bit Left Shift in Three StagesArrows show the data word passing through one row of 2-to-1 muxes per bit of the amount s.
  • I/O
  • Datapath
  • Data
  • Control
An 8-bit left shift in three stagesArrows show the data word passing through one row of 2-to-1 muxes per bit of the amount `s`. io a[7:0] the word io s[2:0] the amount, 0 to 7 datapath Stage 1 shift by 1 if s[0] datapath Stage 2 shift by 2 if s[1] datapath Stage 4 shift by 4 if s[2] io y[7:0] a << s 8 bitss[0]s[1]s[2]
  1. io a[7:0]the word
    • 8 bits → Stage 1
  2. io s[2:0]the amount, 0 to 7
    • s[0] → Stage 1
    • s[1] → Stage 2
    • s[2] → Stage 4
  3. datapath Stage 1shift by 1 if s[0]
    • Stage 2
  4. datapath Stage 2shift by 2 if s[1]
    • Stage 4
  5. datapath Stage 4shift by 4 if s[2]
    • y[7:0]
  6. io y[7:0]a << s
  1. One stage

    Stage 1 is eight muxes. Each picks its own bit or the bit one place to the right, as s[0] says.

  2. Powers of two

    Stage 2 moves by two places and stage 4 by four. Any amount from 0 to 7 is a sum of 1, 2 and 4.

  3. The cost

    Three rows of muxes, so three levels of logic. A 32-bit shifter has five rows.

Read the diagram as text
  • a[7:0]: the word
  • s[2:0]: the amount, 0 to 7
  • Stage 1: shift by 1 if s[0]
  • Stage 2: shift by 2 if s[1]
  • Stage 4: shift by 4 if s[2]
  • y[7:0]: a << s
  • a[7:0] → Stage 1: 8 bits
  • Stage 1 → Stage 2
  • Stage 2 → Stage 4
  • Stage 4 → y[7:0]
  • s[2:0] → Stage 1: s[0]
  • s[2:0] → Stage 2: s[1]
  • s[2:0] → Stage 4: s[2]

You do not write the stages. a << s builds them. The count is one level for each bit of the amount.

Widtha << ssigned a >>> srotate left (next section)
826 cells, 3 levels21 cells, 3 levels24 cells, 3 levels
1667 cells, 4 levels60 cells, 4 levels64 cells, 4 levels
32164 cells, 5 levels155 cells, 5 levels160 cells, 5 levels
64429 cells, 8 levels382 cells, 8 levels384 cells, 6 levels

Measured on this flow. The rotate is exactly W muxes per stage: 8 times 3, 16 times 4, 32 times 5, 64 times 6. At 64 bits the two shifts came out deeper than their six stages.

Rotates

A rotate is a shift whose lost bits come back in at the other end. SystemVerilog has no rotate operator.

A rotate by a constant is a concatenation, and so it is wiring: {a[5:0], a[7:6]} rotates left by 2. A rotate by a signal needs one trick.

Two shifts and an OR

assign y = (a << s) | (a >> (4'd8 - s));

Correct for every amount. 74 cells and 7 levels on this flow: two shifters and a subtract.

One shift of a double-width vector

module rol8 (
  input  logic [7:0] a,
  input  logic [2:0] s,
  output logic [7:0] y
);
  logic [15:0] d;
  assign d = {a, a} << s;        // a joined to itself, then one shift
  assign y = d[15:8];            // the top half is a rotated left by s
endmodule

The same results. 24 cells and 3 levels: eight muxes in each of three stages.

Join the vector to itself and shift the pair left. The bits that leave the top copy are replaced by the same bits from the bottom copy. For a right rotate, shift the pair right and take the bottom half.

Streaming: Reorder with No Gates

The streaming operator {<<N{x}} cuts x into blocks of N bits and writes the blocks in the opposite order. With no N the blocks are single bits.

Verilator 5.052 prints rev=01001011 swp=cdab3412 nib=dcba4321 same=1234abcd c=5ad2.
module tb;
  logic [31:0] a = 32'h1234_abcd, swp, nib, same;
  logic [7:0]  b = 8'b1101_0010, rev;
  logic [15:0] c;
  initial begin
    rev  = {<<{b}};              // 1-bit blocks: reverse the bits
    swp  = {<<8{a}};             // 8-bit blocks: reverse the bytes
    nib  = {<<4{a}};             // 4-bit blocks: reverse the nibbles
    same = {>>{a}};              // left to right: the same order
    c    = {<<8{b, 8'h5a}};      // several items: joined first, then reordered
    $display("rev=%b swp=%h nib=%h same=%h c=%h", rev, swp, nib, same, c);
    $finish(0);
  end
endmodule
FormWhat it doesA use
{<<{x}}reverses the bitsa CRC or a serial port that sends the low bit first
{<<8{x}}reverses the bytes; bits inside a byte keep their orderan endian swap between a bus and a network header
{>>{x}}keeps the orderpacking an array or a struct into a vector
{>>8{lane}} = word;on the left side: unpacks word into the bytes of an arraysplitting a bus into lanes; lane[0] got the top byte

Synthesize a module with the bit reverse, the byte swap and the nibble swap of a 32-bit word. It reports 0 cells and 0 levels. The unpack into four byte lanes is 0 cells too. All of it is wiring.

The Lab: The Sample That Changed Sign

Design brief
PortDirectionWidthMeaning
sampleinput[7:0]a two's complement sample, -128 to 127
shinput[1:0]the scale: divide by 1, 2, 4 or 8
youtput[7:0]sample / 2**sh, rounded toward minus infinity
Latency
combinational
Corner cases
negative samples, and sh at 0. Done when: Run prints y= -16 for -64 with sh 2 and y= -2 for -3 with sh 1, and Synthesize reports 14 cells
  1. Run as shipped

    Line 1 is right: 100 with sh 2 gives 25. Line 2 is right, because a shift by 0 moves nothing. Lines 3 to 5 show 48, 126 and 16 for negative samples.

  2. Find the unsigned operand

    sample is declared logic [7:0], which is unsigned. >>> on it fills with zeros. Lint prints nothing: the code is legal.

  3. Try a fix that fails

    Write assign y = (sh == 2'd0) ? sample : $signed(sample) >>> sh; and Run. The lines do not change. The unsigned arm makes the whole ternary unsigned.

  4. Fix the expression

    Write assign y = $signed(sample) >>> sh; and Run: -64, -16, -2, -16. Synthesize reports 14 cells and 2 levels, all $_MUX_. The shipped version was 17 cells.

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

    >> always fills with zeros. >>> fills with the sign bit, but only when the expression it shifts is signed. On an unsigned operand the two are the same.

  2. What does a shift cost in hardware?

    A shift by a constant is wiring and costs nothing. A shift by a signal is a barrel shifter. It has one row of muxes and one level of logic for each bit of the amount.

  3. How do you rotate a vector by a variable amount?

    Join the vector to itself, shift the pair by the amount and take one half. It costs one barrel shifter. Two shifts and an OR also work, and cost about three times as much on this flow.

Try It

The bench applies five samples and prints y as a signed number and in binary. The first two lines are right. A positive sample has a 0 sign bit, and a shift by 0 moves nothing.

In the last three lines zeros came in at the top, because sample is unsigned. With $signed(sample) the lines read -16, -2 and -16.

Synthesize reports 17 cells and 2 levels for the shipped design: 13 $_MUX_ and 4 gates. The fixed design is 14 cells, all $_MUX_, and 2 levels.

RTLIcarus Verilog · in your browser · Lint: Verilator service · Synthesize: Yosys service
Edit the design, then Run, Lint or Synthesize
Expected: sample= 100 sh=2 | y= 25 (00011001) sample= -64 sh=0 | y= -64 (11000000) sample= -64 sh=2 | y= 48 (00110000) sample= -3 sh=1 | y= 126 (01111110) sample=-128 sh=3 | y= 16 (00010000)

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

Read included file: tb.sv
module tb;
  logic [7:0] sample = 0, y;
  logic [1:0] sh = 0;
  level_scale dut (.*);
  task automatic show(input int v, input int s);
    sample = 8'(v); sh = 2'(s); #1;
    $display("sample=%4d sh=%0d | y=%4d (%b)", $signed(sample), sh, $signed(y), y);
  endtask
  initial begin
    show(100, 2);
    show(-64, 0);
    show(-64, 2);
    show(-3, 1);
    show(-128, 3);
    $finish(0);
  end
endmodule

Check Yourself

Predict the outputThe same 24-bit word goes through a streaming operator twice, with blocks of 8 bits and then of 4 bits. What does the bench print on Verilator?
module tb;
  logic [23:0] a = 24'h123456, y, z;
  initial begin
    y = {<<8{a}};
    z = {<<4{a}};
    $display("%h %h", y, z);
    $finish(0);
  end
endmodule
Spot the bugx holds a signed value but is declared logic [7:0]. Each option divides it by 4, rounding down. The bench checks 100, -64, -1 and 7. Which option fails?
ConceptOn this flow, what does assign y = a << 3; build for an 8-bit a?
ConceptA 32-bit word is shifted left by a 5-bit signal. How many levels of logic did this flow report, and why?
ConceptAn 8-bit a must rotate left by a 3-bit signal s. Which design did this flow build in 24 cells and 3 levels?

Common Mistakes

Wrong Build a one-hot mask as {8'd1 << n} inside braces when n can be 8 or more.

Inside braces nothing widens the shift. It is done at the width of its left operand, so the 1 falls off the top and the mask is 0.

Fix Give the left operand the width of the result you need. In a plain 16-bit assignment the target widens the shift, but a sized operand is clear anywhere.

Before
logic [3:0]  n;            // 0 to 15
logic [15:0] mask;
assign mask = {8'd1 << n}; // 0 for n = 8 to 15
After
logic [3:0]  n;          // 0 to 15
logic [15:0] mask;
assign mask = 16'd1 << n;

Wrong Write a variable rotate as two shifts joined by an OR.

The second shift needs a subtract for its amount, and the flow built 74 cells where one shift builds 24.

Fix Shift the vector joined to itself, {a, a} << s, and take the top half.

Wrong Use x >>> 1 in place of a signed divide by 2.

The shift rounds toward minus infinity and the divide rounds toward zero, so they differ on odd negative values.

Fix Decide the rounding from the brief first. Lesson R1.6 measures both on -3.

Wrong Pass a streaming operator straight to $display or into a larger expression.

A streaming operator has no width of its own, and Verilator stops with "cannot be used in an implicitly cast context".

Fix Assign it to a variable of the width you want, then use the variable.

Remember

  • << and >> fill with zeros. >>> fills with the sign bit only when the whole expression is signed.
  • One unsigned operand, a part-select or an unsigned ternary arm turns >>> into a zero fill.
  • A shift by a constant is wiring: 0 cells. A shift by a signal is a barrel shifter with one mux level per amount bit.
  • Rotate by shifting the vector joined to itself: 24 cells at 8 bits, against 74 for two shifts and an OR.
  • Streaming operators reverse bits or bytes for 0 cells. Assign the result to a sized variable.

Practice

Report a problem with this page