Content deleted Content added
Altered journal. | Use this tool. Report bugs. | #UCB_Gadget |
BrainStack (talk | contribs) Link suggestions feature: 3 links added. |
||
Line 45:
| Assembly: [[RISC-V]] || <code>sll</code>, <code>slli</code><ref>{{Cite web|url=https://github.com/riscv/riscv-isa-manual/releases/download/Ratified-IMAFDQC/riscv-spec-20191213.pdf |archive-url=https://ghostarchive.org/archive/20221009/https://github.com/riscv/riscv-isa-manual/releases/download/Ratified-IMAFDQC/riscv-spec-20191213.pdf |archive-date=2022-10-09 |url-status=live|date=2019-12-13|access-date=2021-08-07|title=The RISC-V Instruction Set Manual, Volume I: Unprivileged ISA|website=[[GitHub]] |pages=18–20}}</ref> || <code>sra</code>, <code>srai</code>
|}
In [[computer programming]], an '''arithmetic shift''' is a [[Bitwise_operation#Bit_shifts|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 numeral system|binary number]]s 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.<ref>
Line 57:
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 2<sup>''n''</sup>. Shifting right by ''n'' bits on a [[two's complement]] ''signed'' binary number has the effect of dividing it by 2<sup>''n''</sup>, 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.<ref>{{cite web|last=Steele Jr|first=Guy|title=Arithmetic Shifting Considered Harmful|url=http://dspace.mit.edu/bitstream/handle/1721.1/6090/AIM-378.pdf |archive-url=https://ghostarchive.org/archive/20221009/http://dspace.mit.edu/bitstream/handle/1721.1/6090/AIM-378.pdf |archive-date=2022-10-09 |url-status=live|publisher=MIT AI Lab|access-date=20 May 2013}}</ref>
For example, in the [[x86 instruction listings|x86 instruction set]], the SAR instruction (arithmetic right shift) divides a signed number by a [[power of two]], rounding towards negative infinity.{{sfn|Hyde|1996|loc=§ 6.6.2.2 SAR}} 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 ==
Line 78:
The (1999) ISO standard for the programming language [[C (programming language)|C]] defines the right shift operator in terms of divisions by powers of 2.{{sfn|ISOIEC9899|1999|loc=§ 6.5.7 Bitwise shift operators}} 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.{{#tag:ref|The C standard was intended to not restrict the C language to either ones' complement or two's complement architectures. In cases where the behaviours of ones' complement and two's complement representations differ, such as this, the standard requires individual C compilers to document the behaviour of their target architectures. The documentation for [[GNU Compiler Collection]] (GCC), for example, documents its behaviour as employing sign-extension.{{sfn|FSF|2008|loc=§ 4.5 Integers implementation}}|group="note"}}
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.{{sfn|ISOCPP20|2020|loc=§ 7.6.7 Shift operators}}
== Applications ==
| |||