Bit shift

A fixed-width left shift discards high bits and inserts low zeros. A logical right shift inserts high zeros; an arithmetic right shift propagates the sign bit. In Java, <<, >>> and >> distinguish these operations. Left shift by $k$ is multiplication by $2^k$ modulo the word modulus.

// Destination: computer-science.bigb

A bit rotation cyclically moves the bits of a fixed-width machine word: positions discarded at one end reappear at the other. A logical shift instead fills vacated positions with zero and discards outgoing bits. Consequently they have different wiring at the edge of a barrel shifter.

An arithmetic right shift propagates the sign bit into the vacated high positions. For a signed two's complement integer, its result is division by $2^k$ rounded down. This differs from C integer division on negative nonmultiples of $2^k$, because that quotient truncates towards zero. Shifting an $n$-bit word arithmetically by $n-1$ produces zero for a nonnegative value and the all-one word, representing $-1$, for a negative value.

A logical right shift moves bits toward less significant positions, discards those shifted out, and fills the high positions with zero. On the unsigned interpretation of a machine word, it computes the quotient in integer division by $2^k$. Indeed, splitting the binary representation after its lowest $k$ bits gives $a=2^{k}q+r$ with $0\le r<2^k$; the retained upper bits represent $q$. A fixed-width left bit shift by $n-k$ followed by a logical right shift by $n-k$ extracts precisely the low $k$ bits, giving the remainder.

A bit shift toward more significant positions, filling low positions with zeros. On an unbounded nonnegative integer, shifting left by $k$ places multiplies it by $2^k$; fixed-width representations may discard overflowing high bits.