Arithmetic shift
An arithmetic shift is a bitwise operation in computer architecture that shifts the bits of a signed binary number left or right by a specified number of positions, while preserving the sign of the number by filling the vacated bit positions with copies of the sign bit (the most significant bit).[1][2] In an arithmetic left shift, bits are moved to the left, the least significant bits are filled with zeros, and bits shifted beyond the most significant position are discarded, effectively multiplying the number by a power of two for positive values but potentially causing overflow for signed representations.[1] For an arithmetic right shift, bits are moved to the right, the most significant bits are filled with the sign bit to maintain the number's sign (replicating 0 for positive numbers and 1 for negative numbers), and the least significant bit is discarded, which performs division by a power of two while rounding toward negative infinity in two's complement systems.[1][3] This contrasts with a logical shift, which always fills vacated positions with zeros regardless of the sign, making it suitable for unsigned integers but altering the sign of signed ones.[1] Arithmetic shifts are fundamental in processor arithmetic logic units (ALUs) for efficient implementation of multiplication and division by powers of two, as well as in applications like fixed-point arithmetic, signal processing, and bit manipulation in embedded systems.[4]Fundamentals
Definition
An arithmetic shift is a bitwise operation that shifts the bits of a binary number left or right by a specified number of positions, with the key characteristic of preserving the sign of the number when operating on signed integers represented in two's complement form.[5][6] In this representation, the most significant bit (MSB) serves as the sign bit: 0 for positive (including zero) and 1 for negative values.[7] To understand arithmetic shifts, consider the binary representation of signed integers using two's complement, the predominant method in modern computing architectures. For an n-bit integer, positive numbers are encoded in standard binary, while negative numbers are formed by inverting all bits of the positive equivalent and adding 1; this allows arithmetic operations to treat positive and negative values uniformly without separate sign handling.[7][8] In an arithmetic left shift, vacated bit positions on the right are filled with zeros. In an arithmetic right shift, vacated bit positions on the left are filled by replicating the sign bit, ensuring the numerical value remains correctly interpreted as signed—zeros for positive numbers and ones for negative ones.[5][9] This contrasts with logical shifts, which always fill with zeros regardless of sign.[6] For example, consider an 8-bit positive integer 00001010₂ (decimal 10). An arithmetic left shift by 1 position yields 00010100₂ (decimal 20), filling the right with 0; a right shift by 1 yields 00000101₂ (decimal 5), filling the left with 0 due to the positive sign.[5] For a negative 8-bit integer like 11110110₂ (decimal -10 in two's complement), a right shift by 1 becomes 11111011₂ (decimal -5), filling the left with 1s to extend the sign and preserve negativity.[6] Left shifts on negative numbers fill with 0 on the right but may cause overflow if the sign bit shifts out.[5] Arithmetic shifts originated in early computer architectures to enable efficient signed arithmetic operations, notably in the IBM System/360 introduced in 1964, where instructions like Shift Right Arithmetic (SRA) and Shift Left Arithmetic (SLA) explicitly preserved the sign bit for fixed-point integers.[10]Comparison to logical shift
The logical shift operation treats the operand as an unsigned integer, filling any vacated bit positions with zeros during both left and right shifts, regardless of the original sign of the value.[11] In contrast, the arithmetic right shift preserves the sign of signed integers by filling vacated positions on the left with copies of the sign bit (0 for positive, 1 for negative), which maintains the numerical value's intended signed magnitude during division-like operations.[11] This difference becomes critical when processing signed data: a logical shift can inadvertently change the sign or produce an incorrect positive value, while an arithmetic shift ensures sign preservation.[12] To illustrate, consider an 8-bit two's complement representation where the value -4 is encoded as 11111100. A right shift by 1 bit using arithmetic shift fills with the sign bit (1), resulting in 11111110 (-2, preserving the negative sign and halving the magnitude). The same operation using logical shift fills with 0, yielding 01111111 (127, an unsigned positive value that alters the sign).[13]| Value | Binary (8-bit) | Operation | Arithmetic Right Shift Result | Logical Right Shift Result |
|---|---|---|---|---|
| Signed -4 | 11111100 | Right by 1 | 11111110 (-2) | 01111111 (127) |
Operations
Left shift
The arithmetic left shift operation moves each bit in a binary number to the left by a specified number of positions n, filling the vacated rightmost bits with zeros while discarding any bits shifted out from the left in fixed-width representations such as registers or words.[13] This behavior is identical for both unsigned and signed integers, as the left shift does not depend on the sign bit for insertion.[15] In two's complement representation for signed integers, an arithmetic left shift by n positions is mathematically equivalent to multiplying the original value x by $2^n, as long as the result does not cause overflow within the fixed bit width.[16] The equation can be expressed as x \ll n = x \times 2^n.[17] This equivalence holds because shifting left effectively scales the positional values of the bits by powers of 2, preserving the signed interpretation until overflow intervenes.[6] For example, consider the 8-bit two's complement representation of the positive integer 5, which is $00000101_2. Performing a left shift by 2 positions yields $00010100_2, equivalent to 20 in decimal, demonstrating multiplication by $2^2 = 4.[13] Similarly, for the negative integer -5, represented as $11111011_2, a left shift by 1 position results in $11110110_2, which is -10 in decimal, corresponding to multiplication by $2^1 = 2.[16] Overflow occurs in signed arithmetic if the shifted result exceeds the representable range for the bit width, potentially causing the sign bit to change and flipping the sign of the value (e.g., a positive number becoming negative or vice versa).[16] For instance, in 4-bit two's complement, shifting 7 ($0111_2) left by 1 produces $1110_2 (-2), as the overflowed bit sets the sign bit to 1.[13] Such behavior underscores the need to check for overflow in arithmetic computations using shifts.[15]Right shift
The arithmetic right shift operation moves the bits of a binary number to the right by a specified number of positions, n, while filling the vacated most significant bits (leftmost) with copies of the original sign bit to preserve the number's sign in two's complement representation.[13] This sign extension ensures that positive numbers remain positive and negative numbers remain negative after the shift.[6] The least significant n bits are discarded (shifted out), effectively truncating the lower-order bits.[18] For positive signed integers, an arithmetic right shift by n bits is equivalent to integer division by $2^n, as the operation aligns with standard unsigned right shifting in this case.[6] However, for negative signed integers, the shift performs a flooring division by $2^n, rounding toward negative infinity rather than toward zero, due to the sign bit replication which adjusts the magnitude downward.[18] For instance, shifting -5 (binary 11111011 in 8-bit two's complement) right by 1 bit yields -3 (11111101), since -5 divided by 2 is -2.5, and flooring gives -3.[6] Consider an 8-bit two's complement example with the positive number 20, represented as 00010100. An arithmetic right shift by 2 bits moves the bits right, fills the left with 0 (sign bit), and discards the last two bits (00), resulting in 00000101, which is 5—equivalent to 20 divided by 4.[13] For the negative number -20, represented as 11101100, the same shift by 2 bits moves the bits right, fills the left with 1 (sign bit), and discards the last two bits (00), yielding 11111011, which is -5—consistent with flooring division of -20 by 4 to -5.[18] This truncation of least significant bits in signed arithmetic thus implements a form of division that prioritizes sign preservation over symmetric rounding.[13]Properties
Sign preservation
In two's complement representation, the arithmetic right shift operation preserves the sign of a signed integer by replicating the sign bit (the most significant bit) into the vacated positions on the left, ensuring that a negative input remains negative and a positive input remains positive.[5][9] For example, the 4-bit two's complement value -4 (binary 1100) shifted right by 1 bit becomes 1110 (-2), with the sign bit '1' replicated to maintain negativity.[5] This replication distinguishes arithmetic right shifts from logical right shifts, which fill with zeros and could alter the sign interpretation.[19] Arithmetic left shifts generally preserve the sign as well, since they fill the least significant bits with zeros and shift the sign bit leftward, but this holds only until overflow occurs, at which point the sign bit may change if the result exceeds the representable range.[5] For instance, in an 8-bit two's complement system, shifting -1 (binary 11111111) left by 1 bit yields 11111110 (-2), preserving the negative sign, but further shifts can lead to overflow where the sign bit flips if the magnitude grows beyond the format's limits.[5] Edge cases highlight the behavior clearly: shifting the all-zero pattern (representing 0) right arithmetically yields 0 regardless of shift amount, as the sign bit is 0 and replicates zeros; conversely, shifting the all-one pattern (representing -1) right replicates 1s, keeping the result as -1.[5] In multi-word integers, such as extending a 32-bit signed value to 64 bits, arithmetic right shifts propagate the sign bit across word boundaries via sign extension, filling higher bits with the replicated sign to maintain the correct negative or positive interpretation in the larger format.[20] These sign preservation properties enable efficient implementation of signed arithmetic operations, such as division by powers of 2, without requiring complex full adders for sign handling, as the replicated bits inherently adjust the magnitude while keeping the sign intact.[5] In contrast, for unsigned integers, the sign bit holds no interpretive meaning, so arithmetic shifts are typically replaced by logical shifts that zero-fill, avoiding unnecessary sign replication.[9]Relation to multiplication and division
The arithmetic left shift operation by n bits on an integer x, denoted x \ll n, is exactly equivalent to multiplication by $2^n, assuming no overflow occurs in the representation.[21] This holds for both signed and unsigned integers, as the shift fills the vacated least significant bits with zeros, effectively scaling the value by the power of two without altering the sign bit's influence in two's complement.[22] In contrast, the arithmetic right shift x \gg n approximates division by $2^n but implements a floor division, always rounding the quotient toward negative infinity. For nonnegative x, this matches the typical integer division semantics of truncation toward zero. However, for negative x, the result differs due to the flooring behavior; for example, in two's complement, -7 \gg 1 = -4, whereas the true division -7 / 2 = -3.5 would truncate to -3 under toward-zero rounding.[18] This discrepancy arises because the sign extension in arithmetic right shift preserves the negative sign while shifting, effectively rounding down rather than toward zero.[23] These differences highlight key non-equivalences in signed arithmetic, particularly in rounding modes across systems. Modern languages like C and C++ specify signed integer division to truncate toward zero, independent of the shift operation's flooring. Arithmetic right shift, however, consistently floors, leading to potential mismatches for negative values unless adjusted.[18] Other modes, such as rounding toward positive or negative infinity, are not natively supported by shifts but can influence division in floating-point contexts or specific hardware. To simulate toward-zero division for n=1 using arithmetic right shift on negative odd integers, a common adjustment adds 1 post-shift when applicable:(x >> 1) + ((x < 0) && (x & 1) ? 1 : 0).[18] This corrects the flooring bias only in cases where the least significant bit indicates a fractional remainder requiring upward adjustment toward zero.
Implementation
In hardware
Arithmetic shifts are implemented in the arithmetic logic unit (ALU) of processors through dedicated shifter circuits that handle bit manipulations efficiently. These circuits often employ multiplexers (MUXes) arranged in layers to form a barrel shifter, enabling variable shift amounts (n) in a single clock cycle by routing bits through multiple stages of selection. For arithmetic right shifts, sign extension is achieved by wiring the sign bit (most significant bit) of the operand to the input lines that fill the vacated high-order positions, preserving the number's sign during the operation.[24][25][26] One of the earliest commercial implementations of arithmetic shifts appeared in the IBM System/360 mainframe architecture, introduced in 1964, which included instructions like Shift Left Arithmetic (SLA) and Shift Right Arithmetic (SRA) in its fixed-point instruction set to support signed integer operations. These instructions were designed to integrate seamlessly with the system's ALU for efficient handling of two's complement arithmetic, marking a significant advancement in hardware support for signed bit shifts.[10][27] In modern processors, arithmetic shifts are supported via specialized instructions that extend to both scalar and vector operations. For instance, the x86 architecture provides the SAR (Shift Arithmetic Right) instruction, which performs right shifts on registers while filling with the sign bit, and SIMD extensions like MMX and SSE include packed variants such as PSRAW for parallel arithmetic right shifts on multiple data elements. Similarly, RISC architectures like ARM incorporate the ASR (Arithmetic Shift Right) instruction, which differs from its logical counterpart LSR (Logical Shift Right) by sign-extending the operand, enabling efficient signed division in resource-constrained environments. In contrast to CISC designs like x86, which may combine shifts with other operations in complex instructions, RISC approaches prioritize simple, single-cycle shifts to enhance pipeline efficiency and reduce power consumption in embedded systems.[28][29]In programming languages
In C and C++, the right-shift operator>> performs an arithmetic shift for signed integer types, preserving the sign bit by filling vacated positions with copies of the sign bit, while it performs a logical shift for unsigned types by filling with zeros.[30] This behavior for signed integers was implementation-defined prior to C++20 but has been standardized as arithmetic since then, rounding toward negative infinity for negative values.[30] To ensure logical shifting on signed types, programmers often cast to unsigned explicitly, such as (unsigned int)x >> n.[30]
In Java, the >> operator implements an arithmetic right shift for all integer types, sign-extending the result to preserve the sign, while the >>> operator provides a logical right shift by zero-filling regardless of sign.[31] For positive values, this corresponds to truncation toward zero in division by powers of two; for negative values, it truncates toward negative infinity due to sign extension.[31] The Java Language Specification defines this precisely for 32-bit int and 64-bit long types, with the shift amount masked to the appropriate bit width (five bits for int, six for long).[31]
Python's >> operator performs an arithmetic right shift on integers, treating them as arbitrary-precision two's complement values and filling with the sign bit for negative numbers, equivalent to floor division by $2^n.[32] In JavaScript, bitwise operators including >> convert operands to 32-bit signed integers before operating, resulting in an arithmetic right shift that preserves the sign via sign extension; the result is then converted back to a floating-point number.[33]
Portability challenges arise primarily in C and C++, where the behavior of >> on signed negative integers remains implementation-defined in C (as per ISO C99 and later), potentially leading to logical instead of arithmetic shifts on some platforms, though most common compilers use arithmetic.[34] Endianness does not affect shift operations directly, but multi-byte integer representations can complicate sign extension across architectures if shifts exceed the type's bit width, often requiring explicit masking of the shift amount to avoid undefined behavior.[30] To achieve portable arithmetic right shifts in C, one common approach is to cast to unsigned, perform the shift, and adjust based on the original sign bit.[35]
When using arithmetic right shifts for signed integer division by powers of two, the truncation toward negative infinity for negative values can deviate from toward-zero semantics in some languages, necessitating adjustments for consistent "true" division.[35] For positive or unsigned values seeking rounding up (ceiling division), a portable idiom in C/C++ and similar languages is (x + ((1U << n) - 1)) >> n, which adds the appropriate bias before shifting to handle the truncation correctly without branches.[35] In Java and Python, where arithmetic shifts are reliably defined, such fixes are less critical but may still be applied for specific rounding modes.[31]