15.4 Shifters: Logical, Arithmetic, and Rotate
Distinguish logical shift, arithmetic shift, and rotate operations, and explain why arithmetic right shift preserves the sign bit while logical right shift does not.
A shifter repositions the bits of an operand left or right by a specified number of positions, and is one of the ALU's core operations alongside arithmetic and bitwise logic. Shifting looks like a simple mechanical rearrangement of bits, but the choice of what fills the vacated positions — and whether that choice preserves a signed number's meaning — is a frequent source of subtle bugs, which is exactly why digital design distinguishes several distinct kinds of shift rather than treating 'shift' as one operation.
Logical Shifts
A logical shift left (LSL) moves every bit one or more positions toward the most significant end, discarding bits shifted out past the MSB and filling the newly vacated least-significant positions with 0s. A logical shift right (LSR) moves every bit toward the least significant end, discarding bits shifted out past the LSB and filling the newly vacated most-significant positions with 0s. Logical shifts treat the operand purely as an unsigned bit pattern — they make no attempt to preserve any signed interpretation of the value, which is exactly correct when the operand genuinely represents an unsigned quantity, but produces a wrong result if it was meant to represent a negative signed number.
Shifting left by one position is mathematically equivalent to multiplying an unsigned value by 2 (as long as no significant bit is lost off the top), and shifting right by one position is equivalent to unsigned integer division by 2 (discarding the remainder) — this equivalence generalizes: shifting left by k positions multiplies by 2^k, and shifting right by k positions divides by 2^k, for unsigned values.
• Logical shift left (LSL): bits move toward MSB, 0s fill from the LSB side. • Logical shift right (LSR): bits move toward LSB, 0s fill from the MSB side. • Logical shifts treat the operand as unsigned — no sign preservation. • LSL by k ≈ multiply by 2^k (unsigned); LSR by k ≈ divide by 2^k (unsigned, truncating).
Arithmetic Shifts and Rotates
Arithmetic shift right (ASR) preserves the sign bit in two's-complement representation; logical right shift inserts zeros. Concretely, ASR fills the vacated most-significant positions with copies of the original sign bit (0 for a positive number, 1 for a negative number) rather than always inserting 0 — this keeps a negative two's-complement number negative after shifting, correctly implementing signed division by a power of two (rounding toward negative infinity). There is no separate 'arithmetic shift left' distinct from logical shift left in most architectures, because shifting left toward the MSB is identical whether the operand is signed or unsigned — the sign-preservation issue only arises when shifting right, since that's the direction that would otherwise expose the vacated sign position to an incorrect fill value.
A rotate (ROL/ROR) is different from both logical and arithmetic shifts: instead of discarding bits that fall off one end and filling the other end with 0s or a sign copy, a rotate wraps those bits around to the opposite end, so no information is ever lost — every bit that leaves one side reappears at the other. Some architectures offer a rotate-through-carry variant, where the carry flag itself is included as an extra bit in the rotation, letting a rotate operation move a bit into or out of the carry flag on each shift — useful for multi-word shifts and certain checksum/CRC computations.
• Arithmetic shift right (ASR): fills vacated MSB positions with copies of the sign bit — preserves sign for two's-complement numbers. • Logical shift right (LSR): always fills vacated MSB positions with 0 — does not preserve sign. • Rotate (ROL/ROR): bits wrapped around to the opposite end — no information is lost. • Rotate-through-carry: includes the carry flag as an extra bit in the rotation.
Barrel Shifters and Real-World Applications
A naive shifter built from cascaded 1-bit shift stages needs k clock cycles (or k stages of combinational logic) to shift by k positions. A barrel shifter instead uses a network of multiplexers arranged so that any shift amount, from 0 up to the full operand width, can be performed in a single operation — trading additional multiplexer hardware for constant-time shifting regardless of how far the shift needs to go. Barrel shifters are standard in modern CPU ALUs precisely because variable, arbitrary-amount shifts are common (both in explicit shift instructions and internally, such as for floating-point normalization) and a fixed, single-cycle latency is far preferable to a shift time that depends on the shift amount.
Shift and rotate operations appear constantly in real code: multiplying or dividing by powers of two via shifts is a classic low-level optimization, packing/unpacking bit-fields relies on shifts to move a field into or out of position, cryptographic algorithms and hash functions use rotates extensively (since rotation is reversible and mixes bits without losing information), and signed division by a power of two in compiled code typically uses an arithmetic shift right specifically to preserve correct rounding behavior for negative operands.
Shift and rotate behavior summary
There is no separate arithmetic shift left distinct from logical shift left — sign-preservation only matters when shifting right.
LSL (logical shift left): vacated LSBs <- 0
LSR (logical shift right): vacated MSBs <- 0
ASR (arithmetic shift right): vacated MSBs <- copy of original sign bit
ROL (rotate left): bit shifted out of MSB -> reappears at LSB
ROR (rotate right): bit shifted out of LSB -> reappears at MSBCode Examples
Every bit moves one position toward the MSB; the original bit 7 (0) is discarded off the top, and a new 0 fills the vacated LSB position. As an unsigned value, 00110100 (52) becomes 01101000 (104) — exactly double, confirming that a logical left shift by one is equivalent to multiplying an unsigned value by 2. Expected result: 01101000
00110100 << 1 = 01101000 — equivalent to ×2 for this unsigned value.
The operand 1111_0000 represents −16 in 8-bit two's complement. A logical shift right fills the vacated MSB with 0, destroying the sign and turning the value into a large positive number (+120) — clearly wrong if −16 was meant to stay negative. An arithmetic shift right instead copies the original sign bit (1) into the vacated MSB position, correctly producing 1111_1000 = −8, exactly −16 ÷ 2 as expected for a signed number. Expected result: LSR: 0111_1000 (wrong for signed), ASR: 1111_1000 (correct, -8)
Arithmetic shift right preserves the sign bit; logical shift right always inserts 0, corrupting negative values.
Common mistake: Using a logical shift right on a signed (two's-complement) value expecting it to behave like signed division — it silently corrupts negative numbers by destroying the sign bit.
00110100 << 1
= 01101000Value (8-bit two's complement) = 1111_0000 (-16 in decimal)
Logical shift right by 1 (LSR): 0111_1000 (+120 — WRONG as signed!)
Arithmetic shift right by 1 (ASR): 1111_1000 (-8 — correct signed /2)Rotate left: bits wrap around, nothing is lost
Unlike a logical or arithmetic shift, a rotate never discards information — every bit that leaves one end reappears at the other.
Before: 1 0 1 1 0 0 1 0
┌───────────────┐
│ rotate left │
└───────────────┘
After: 0 1 1 0 0 1 0 1 (the MSB that fell off reappears at the LSB)Important Rules
Logical shift left/right fill vacated bits with 0, treating the operand as unsigned.
Arithmetic shift right preserves the sign bit in two's-complement representation; logical right shift inserts zeros.
Rotate (ROL/ROR) wraps bits around to the opposite end — no bits are ever discarded.
A barrel shifter uses multiplexer networks to perform any shift amount in a single operation, avoiding a per-bit-of-shift delay.
Shift left by k ≈ multiply by 2^k; arithmetic shift right by k ≈ signed divide by 2^k.
Where shifters show up
Compilers replace multiplication/division by powers of two with shifts as a standard optimization, bit-field packing in hardware registers and network protocols relies on shifts to position values, cryptographic hash functions and CRC computations use rotates extensively, and CPU ALUs universally include a barrel shifter to perform any of these shift or rotate operations in a single cycle.
Using a logical shift right to divide a signed (negative) two's-complement number by two.
Use an arithmetic shift right for signed values — it copies the sign bit into the vacated MSB positions, correctly preserving the number's sign and producing correct signed division behavior.
Arithmetic right shift preserves the sign bit in two's-complement representation; logical right shift inserts zeros — using the wrong one on a signed value silently turns a negative number into a large, incorrect positive number.
What fills the vacated bit positions during an arithmetic shift right of a two's-complement number? A. Always 0 B. Always 1 C. A copy of the original sign bit D. The value of the carry flag
C. A copy of the original sign bit — Arithmetic shift right preserves the sign bit in two's-complement representation by filling each vacated most-significant position with a copy of the original sign bit — 0 for a positive number, 1 for a negative number — which is exactly what a logical right shift (always inserting 0) fails to do.
How does a rotate operation differ fundamentally from a logical or arithmetic shift? A. Rotate only works on signed numbers B. Rotate discards bits shifted off one end, exactly like logical shift C. Rotate wraps bits shifted off one end around to the opposite end, so no information is ever lost D. Rotate can only move bits by exactly one position
C. Rotate wraps bits shifted off one end around to the opposite end, so no information is ever lost — Unlike logical shifts (which fill with 0) or arithmetic shifts (which fill with a sign-bit copy) — both of which discard the bit that falls off the far end — a rotate wraps that departing bit around to reappear at the opposite end, preserving every original bit within the word.
An 8-bit signed value is 1110_0000 (which is −32 in two's complement). Compute the result of an arithmetic shift right by 2, and verify it equals −32 ÷ 4 = −8.
1110_0000 arithmetic-shifted right by 2 gives 1111_1000 (the two vacated MSB positions are filled with the sign bit, 1). Interpreting 1111_1000 as signed two's complement: invert and add 1 → 0000_1000 = 8, so the value is −8 — exactly −32 ÷ 4 = −8, confirming the arithmetic shift correctly performed signed division by 4.
Shift the bits right by two positions and fill the two newly-vacated MSB positions with copies of the original sign bit (1).