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.
- Cycle 0
−8 is f8. On an unsigned value
>>>shifts in zeros, so the result is 3e = 62, the same as>>. - 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_0010 | Written as | Result |
|---|---|---|
| logical left by 2 | x << 2 | 11001000 |
| logical right by 2 | x >> 2 | 00101100 |
| arithmetic right by 2 (x signed) | xs >>> 2 | 11101100 |
| 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.
- I/O
- Datapath
- Data
- Control
- 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
- data now at 2: Stage 1 → Stage 2
- Stage 2: n[1] = 0
This stage passes the word unchanged.
Follow the calls, values and waits
- data now at 2: Stage 2 → Stage 4
- 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
- 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.
| hi | lo | Result: low N bits of {hi, lo} >> n |
|---|---|---|
| all 0 | x | logical right shift of x |
| N copies of x's sign bit | x | arithmetic right shift of x |
| x | x | rotate right of x |
| the next word | x | a window across two words, as in a byte stream |
One right shifter of 2N bits covers every right shift and rotate.
Asked in interviews
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 >>.
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.
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.
Synthesize the design to measure its cells and inspect the mapped gates.
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 wrongOriginal 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
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.
logic [7:0] raw;
assign q = raw >>> 2;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.