Arithmetic shift

related topics
{math, number, function}
{style, bgcolor, rowspan}
{system, computer, user}
{government, party, election}

In computer programming, an arithmetic shift is a shift operator, sometimes known as a signed shift (though it is not restricted to signed operands). For binary numbers it is a bitwise operation that shifts all of the bits of its operand; every bit in the operand is simply moved a given number of bit positions, and the vacant bit-positions are filled in. Instead of being filled with all 0s, as in logical shift, when shifting to the right, the leftmost bit (usually the sign bit in signed integer representations) is replicated to fill in all the vacant positions (this is a kind of sign extension).

Arithmetic shifts can be useful as efficient ways of performing multiplication or division of signed integers by powers of two. Shifting left by n bits on a signed or unsigned binary number has the effect of multiplying it by 2n. Shifting right by n bits on a two's complement signed binary number has the effect of dividing it by 2n, but it always rounds down (towards negative infinity). This is different from the way rounding is usually done in signed integer division (which rounds towards 0). This discrepancy has led to bugs in more than one compiler.

For example, in the x86 instruction set, the SAR instruction (arithmetic right shift) divides a signed number by a power of two, rounding towards negative infinity.[1] However, the IDIV instruction (signed divide) divides a signed number, rounding towards zero. So a SAR instruction cannot be substituted for an IDIV by power of two instruction nor vice versa.

History and details

The formal definition of an arithmetic shift, from Federal Standard 1037C is that it is:

An important word in the FS 1073C definition is "usually". Arithmetic left shifts are equivalent to multiplication by a (positive, integral) power of the radix (e.g. a multiplication by a power of 2 for binary numbers). Arithmetic left shifts are, with one exception, identical in effect to logical left shifts. The exception is the minor trap that arithmetic shifts may trigger arithmetic overflow whereas logical shifts do not. However, arithmetic right shifts are major traps for the unwary.

It is frequently stated that arithmetic right shifts are equivalent to division by a (positive, integral) power of the radix (e.g. a division by a power of 2 for binary numbers), and hence that division by a power of the radix can be optimized by implementing it as an arithmetic right shift. (A shifter is much simpler than a divider. On most processors, shift instructions will execute more quickly than division instructions.) Steele quotes a large number of 1960s and 1970s programming handbooks, manuals, and other specifications from companies and institutions such as DEC, IBM, Data General, and ANSI that make such statements. However, as Steele points out, they are all wrong.

Arithmetic right shifts are only equivalent to division by a power of the radix on an "N-1's-complement" machine (for radix "N"). Arithmetic shifts of binary numbers are only equivalent to division by a power of 2 when the ones' complement representation of signed numbers is being used, for example.

This description has been erroneously brought over from the older one's complement architectures to newer two's complement architectures. But with two's complement binary number representations, arithmetic right shift is not equivalent to division by a power of 2. For negative numbers, the equivalence breaks down. The most trivial example of this is the arithmetic right shift of the number -1 (which is represented as all ones) in a two's complement representation, which yields -1.

Full article ▸

related documents
Zorn's lemma
Linear cryptanalysis
Local field
Codomain
Arithmetic function
Intermediate value theorem
Group isomorphism
Distributivity
Hahn–Banach theorem
Epimorphism
Mathematical singularity
Five lemma
Chomsky hierarchy
Real analysis
P-complete
Pointless topology
Dual number
Coprime
Dedekind cut
Lambert W function
ZPP
Tree (graph theory)
Shannon–Fano coding
Conjugacy class
Nial
Grep
Upper and lower bounds
Soundness
Cofinality
SECD machine