From Surf Wiki (app.surf) — the open knowledge base

Arithmetic shift

Shift operator in computer programming

A right arithmetic shift of a binary number by 1. The empty position in the most significant bit is filled with a copy of the original MSB.

Language or processor	Left	Right
ActionScript 3, Java, JavaScript, Python, PHP, Ruby, C, [C++](c),D, C#, Go, Julia,
Rust (signed types only),
Swift (signed types only)The ` ` operator in C and C++ is not necessarily an arithmetic shift. Usually it is only an arithmetic shift if used with a signed integer type on its left-hand side. If it is used on an unsigned integer type instead, it will be a logical shift.	`	` `
Ada	` Shift_Left `	` Shift_Right_Arithmetic `
Kotlin	` shl `	` shr `
Fortran	` SHIFTL `	` SHIFTA `Fortran 2008.
Standard ML	`	` ~ `
Verilog	`	` `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.
OpenVMS macro language	@
Scheme	`arithmetic-shift`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.
Common Lisp	`ash`
OCaml	`lsl`	`asr`
Haskell	`Data.Bits.shift`
VHDL	`sla`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. While this is an exact mirror image of the arithmetic right shift, it is not the conventional definition of the operator, and is not equivalent to multiplication by a power of 2. In the VHDL 2008 standard this strange behavior was left unchanged (for backward compatibility) for argument types that do not have forced numeric interpretation (e.g., BIT_VECTOR) but 'SLA' for unsigned and signed argument types behaves in the expected way (i.e., rightmost positions are filled with zeros). VHDL's shift left logical (SLL) function does implement the aforementioned 'standard' arithmetic shift.	`sra`
Assembly: Z80	`SLA`	`SRA`
Assembly: x86	`SAL`	`SAR`
Assembly: 68k	`ASL`	`ASR`
Assembly: RISC-V	`sll`, `slli`	`sra`, `srai`

In computer programming, an arithmetic shift is a shift operator, sometimes termed a signed shift (though it is not restricted to signed operands). The two basic types are the arithmetic left shift and the arithmetic right shift. 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).

Some authors prefer the terms sticky right-shift and zero-fill right-shift for arithmetic and logical shifts respectively. Thomas R. Cain and Alan T. Sherman. "How to break Gifford's cipher". Section 8.1: "Sticky versus Non-Sticky Bit-shifting". Cryptologia. 1997.

Arithmetic shifts can be useful as efficient ways to perform 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 a number of compilers.

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. 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.

Formal definition

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".

Non-equivalence of arithmetic right shift and division

However, arithmetic right shifts are major traps for the unwary, specifically in treating rounding of negative integers. For example, in the usual two's complement representation of negative integers, −1 is represented as all 1's. For an 8-bit signed integer this is 1111 1111. An arithmetic right-shift by 1 (or 2, 3, ..., 7) yields 1111 1111 again, which is still −1. This corresponds to rounding down (towards negative infinity), but is not the usual convention for division.

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 faster than division instructions.) Large number of 1960s and 1970s programming handbooks, manuals, and other specifications from companies and institutions such as DEC, IBM, Data General, and ANSI make such incorrect statements.

Logical right shifts are equivalent to division by a power of the radix (usually 2) only for positive or unsigned numbers. Arithmetic right shifts are equivalent to logical right shifts for positive signed numbers. Arithmetic right shifts for negative numbers in N's complement (usually two's complement) is roughly equivalent to division by a power of the radix (usually 2), where for odd numbers rounding downwards is applied (not towards 0 as usually expected).

Arithmetic right shifts for negative numbers are equivalent to division using rounding towards 0 in ones' complement representation of signed numbers as was used by some historic computers, but this is no longer in general use.

Handling the issue in programming languages

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

Like C, C++ had an implementation-defined right shift for signed integers until C++20. Starting in the C++20 standard, right shift of a signed integer is defined to be an arithmetic shift.

Applications

In applications where consistent rounding down is desired, arithmetic right shifts for signed values are useful. An example is in downscaling raster coordinates by a power of two, which maintains even spacing. For example, right shift by 1 sends 0, 1, 2, 3, 4, 5, ... to 0, 0, 1, 1, 2, 2, ..., and −1, −2, −3, −4, ... to −1, −1, −2, −2, ..., maintaining even spacing as −2, −2, −1, −1, 0, 0, 1, 1, 2, 2, ... In contrast, integer division with rounding towards zero sends −1, 0, and 1 all to 0 (3 points instead of 2), yielding −2, −1, −1, 0, 0, 0, 1, 1, 2, 2, ... instead, which is irregular at 0.

Notes

References

Cross-reference

Sources used

References

"Bit manipulation - Dlang Tour".
"Operator Expressions: Arithmetic and Logical Binary Operators".
"Annotated Ada 2012 Reference Manual".
"Z80 Assembler Syntax".
(2019-12-13). "The RISC-V Instruction Set Manual, Volume I: Unprivileged ISA".
Steele Jr, Guy. "Arithmetic Shifting Considered Harmful". MIT AI Lab.

Info: Wikipedia Source

This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page.

binary-arithmetic operators-(programming)

Want to explore this topic further?

Ask Mako anything about Arithmetic shift — get instant answers, deeper analysis, and related topics.

Research with Mako

Free with your Surf account

Content sourced from Wikipedia, available under CC BY-SA 4.0.

This content may have been generated or modified by AI. CloudSurf Software LLC is not responsible for the accuracy, completeness, or reliability of AI-generated content. Always verify important information from primary sources.

Report