Shift Operations

Shifting a binary number left by one position is the cheapest operation in digital design: it costs no gates at all. You relabel the wires. The wire that was bit 2 becomes bit 3, bit 1 becomes bit 2, and so on, and the vacated bit 0 is tied to ground. No logic, no delay, no power.

It works because of positional notation. The value is $\sum_i b_i 2^i$, and moving every bit from position $i$ to $i + 1$ turns that into $\sum_i b_i 2^{i+1}$, which is twice the original. Nothing was computed. The bits were just given new weights.

This is used constantly. Address arithmetic like base + 4 * index is a shift by two and an add. DSP filter coefficients are often chosen as powers of two so that a multiply becomes a shift. Floating-point alignment, checksums, and hash and cipher round functions all shift and rotate. For a fixed amount the hardware is free; the only thing to get right is what happens at the ends, and that depends on whether the value is signed.

Definitions

For an $N$-bit value $x$ and a shift of $k$:

$$x \ll k = x \cdot 2^k \qquad x \gg k \approx x / 2^k$$

The left shift is exact for signed and unsigned values alike as long as nothing overflows. The right shift depends on whether the value is signed, and there are two versions of it. Nearly every shift bug comes from using the wrong one.

Logical shift left

Move every bit $k$ places towards the MSB, fill the vacated low bits with 0, and lose whatever falls off the top (or catch it in the carry flag). Multiplies by $2^k$ for both interpretations, provided the result fits.

	Binary	Unsigned	Signed
before	0011 0100	52	+52
after LSL 2	1101 0000	208	−48

The unsigned result is correct. The signed one overflowed: a 0 in the top bit became a 1 and the value now reads as negative. For unsigned values the shift is exact only if the top $k$ bits were zero; for signed values only if the top $k + 1$ bits were all equal.

Logical shift right

Move every bit $k$ places towards the LSB, fill the vacated high bits with 0, and drop what falls off the bottom. This divides an unsigned value by $2^k$, rounding towards zero. It does not correctly divide a negative two’s complement value:

$$11111000_2 \xrightarrow{\text{LSR 1}} 01111100_2$$

The input is −8. Divided by 2 it should be −4, which is $11111100$. LSR gives $01111100 = +124$. The zero shifted into the top destroyed the sign.

Arithmetic shift right

Same as LSR except that the vacated high bits are filled with copies of the original sign bit. This is sign extension, and it gives a correct signed division by $2^k$, rounding towards negative infinity:

$$11111000_2 \xrightarrow{\text{ASR 1}} 11111100_2 = -4$$

For positive values ASR and LSR are identical, since the sign bit being copied in is 0. The difference shows only for negative values.

Value	Binary	LSR 1	ASR 1
+12	0000 1100	0000 0110 = +6	0000 0110 = +6
−8	1111 1000	0111 1100 = +124, wrong	1111 1100 = −4
−1	1111 1111	0111 1111 = +127, wrong	1111 1111 = −1

The last row is worth a look: $-1/2$ rounded towards negative infinity is −1, and ASR gives that.

The rule is short. LSR for unsigned division, ASR for signed division. The hardware differs only in what is wired into the top bits.

There is no separate arithmetic shift left; shifting left fills with zeros either way and some instruction sets simply have two names for the same operation.

Rotates

A rotate loses nothing: bits that leave one end come back in at the other. Rotate left moves towards the MSB and the bit leaving the top re-enters at the bottom; rotate right is the reverse. A common variant, rotate through carry, passes the outgoing bit into the carry flag and brings the previous carry flag in at the other end, which is how a value spread across two registers is shifted as one.

Rotates are the core of a lot of cryptographic hardware. The SHA-256 compression function rotates 32-bit words by fixed amounts such as 2, 13 and 22 bits, and AES’s ShiftRows step rotates the bytes of each row. They are chosen precisely because a rotate mixes bit positions without losing anything. They also appear in CRC circuits and in multi-word arithmetic.

Figure 1 shows all four operations on one 8-bit value.

In hardware

For a constant shift there are no gates. The synthesizer turns the shift into routing and it disappears from the netlist. A compiler knows this too: for x * 8 it emits a shift, and for x * 6 it may emit (x << 2) + (x << 1), two free shifts and one add, because that is still cheaper than a multiplier.

Operation	Gates	Delay
LSL, LSR, ASR, ROL, ROR by a constant	none	0
shift by a variable amount, $N$ bits	a barrel shifter	$\log_2 N$ mux delays

The second row is the subject of the next article. Once the shift amount is a run-time value, wires cannot rearrange themselves and you need actual logic.

A useful habit for constant multiplications that are not powers of two is to split them into powers of two: $x \times 10 = (x \ll 3) + (x \ll 1)$, two free shifts and one adder. Synthesis tools do this on their own for small constants, but it is worth knowing when you are counting FPGA resources by hand.

Practice Exercise

Problem 1. Apply ASR 3 and LSR 3 to the 8-bit value $10110000$. Which is right for a signed interpretation?

Solution

Unsigned the value is 176; signed it is −80.

LSR 3: $00010110 = 22$. Correct for unsigned, $176 / 8 = 22$. Wrong for signed.

ASR 3: $11110110$, which is −10. Correct for signed, $-80 / 8 = -10$. The three bits shifted out were zero, so the division was exact; had they not been, ASR would have rounded towards negative infinity.

Problem 2. Compute $x \times 12$ for an 8-bit unsigned $x$ using only shifts and adders.

Solution

$12 = 8 + 4$, so $x \times 12 = (x \ll 3) + (x \ll 2)$: two free shifts and one adder. The result can be as large as $255 \times 12 = 3060$, so the adder needs to be 12 bits wide. $12 = 16 - 4$ also works, with a subtractor.

Problem 3. Rotate the 4-bit value $1011$ right by one. What do you get after four such rotations?

Solution

$1011 \to 1101 \to 1110 \to 0111 \to 1011$. After $N$ rotations of an $N$-bit value you are back where you started, since a rotate loses nothing.

In the next article we build the circuit that shifts by any amount from 0 to $N - 1$ in a fixed number of gate delays, the barrel shifter.