Arithmetic shift

Arithmetic shift

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.

Arithmetic shifts can be useful as efficient ways 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 2"n". Shifting right by "n" bits on a two's complement "signed" binary number has the effect of dividing it by 2"n", 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. [ - SAR instruction] 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::A shift, applied to the representation of a number in a fixed radix numeration system and in a fixed-point representation system, and in which only the characters representing the fixed-point part of the number are moved. An arithmetic shift is usually equivalent to multiplying the number by a positive or a negative integral power of the radix, except for the effect of any rounding; compare the logical shift with the arithmetic shift, especially in the case of floating-point representation.

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 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 one's 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.

The (1999) ISO standard for the C programming language defines the C language's right shift operator in terms of divisions by powers of 2. Because of the aforementioned non-equivalence, the standard explicitly excludes from that definition the right shifts of signed numbers that have negative values. It doesn't specify the behaviour of the right shift operator in such circumstances, but instead requires each individual C compiler to specify the behaviour of shifting negative values right.fn|6

On an "N's-complement" architecture (for radix "N") an arithmetic shift is equivalent to a division that rounds "towards negative infinity", not towards zero. Donald Knuth describes this in terms of a floor function.


* The VHDL arithmetic left shift operator is unusual. Instead of filling the LSB of the result with zero, it copies the original LSB into the new LSB. Whilst this is an exact mirror image of the arithmetic right shift, whereas the conventional definition of the operator is not, it is not the conventional definition of the operator, and is not equivalent to multiplication by a power of 2.
* The Verilog arithmetic right shift operator only actually performs an arithmetic shift if the first operand is signed. If the first operand is unsigned, the operator actually performs a "logical" right shift.
* The >> operator in C and C++ is not necessarily an arithmetic shift. Usually it is only an arithmetic shift if used on a signed integer type; but if it is used on an unsigned integer type, it will be a logical shift.
* In the OpenVMS macro language whether an arithmetic shift is a left or a right shift is determined by whether the second operand is positive or negative. This is unusual. In most programming languages the two directions have distinct operators, with the operator specifying the direction, and the second operand is implicitly positive. (Some languages, such as Verilog, require that negative values be converted to unsigned positive values. Some languages, such as C and C++, do not have defined behaviours if negative values are used.)
* In Scheme arithmetic-shift can be both left and right shift, depending on the second operand, very similar to the OpenVMS macro language, although R6RS Scheme adds both -right and -left variants. arimethic-shift in Scheme is not even an operator itself, it is a normal procedure returning the shifted value.
* The C standard was intended to not restrict the C language to either one's complement or two's complement architectures. In cases where the behaviours of one's complement and two's complement representations differ, such as this, the standard requires individual C compilers to document the actual behaviour of their target architectures.



Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • arithmetic shift — aritmetinis postūmis statusas T sritis automatika atitikmenys: angl. arithmetic shift; arithmetical shift vok. arithmetische Verschiebung, f; Stellenwertverschiebung, f rus. арифметический сдвиг, m pranc. décalage arithmétique, m …   Automatikos terminų žodynas

  • Shift — generally means to change (position). Shift may refer to: * Gear shift, to change gears in a car * Shift work, an employment practice * Shift (music), a change of level in music * Shift (magazine), a former Canadian technology and culture… …   Wikipedia

  • Shift register — In digital circuits a shift register is a group of flip flops set up in a linear fashion which have their inputs and outputs connected together in such a way that the data is shifted down the line when the circuit is activated. Shift registers… …   Wikipedia

  • Logical shift — In computer science, a logical shift is a shift operator that shifts all the bits of its operand. Unlike an arithmetic shift, a logical shift does not preserve a number s sign bit or distinguish a number s exponent from its mantissa; every bit in …   Wikipedia

  • Circular shift — In combinatorial mathematics, a circular shift is the operation of rearranging the entries in a tuple, either by moving the final entry to the first position, while shifting all other entries to the next position, or by performing the inverse… …   Wikipedia

  • arithmetical shift — aritmetinis postūmis statusas T sritis automatika atitikmenys: angl. arithmetic shift; arithmetical shift vok. arithmetische Verschiebung, f; Stellenwertverschiebung, f rus. арифметический сдвиг, m pranc. décalage arithmétique, m …   Automatikos terminų žodynas

  • Finite field arithmetic — Arithmetic in a finite field is different from standard integer arithmetic. There are a limited number of elements in the finite field; all operations performed in the finite field result in an element within that field.While each finite field is …   Wikipedia

  • Carry (arithmetic) — In elementary arithmetic a carry is a digit that is transferred from one column of digits to another column of more significant digits during a calculation algorithm. It is a central part of traditional mathematics, but is often omitted from the… …   Wikipedia

  • Bitwise operation — In computer programming, a bitwise operation operates on one or two bit patterns or binary numerals at the level of their individual bits. On most microprocessors, bitwise operations are sometimes slightly faster than addition and subtraction… …   Wikipedia

  • Booth's multiplication algorithm — is a multiplication algorithm that multiplies two signed binary numbers in two s complement notation.ProcedureBooth s algorithm involves repeatedly adding one of two predetermined values A and S to a product P , then performing a rightward… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”