Arithmetic shift operators in various programming languages
| Language | Left | Right |
| 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. 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. In the VHDL 2008 standard this strange behavior was left unchanged (for backwards 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 SLL (Shift Left Logical) function does implement the aforementioned 'standard' arithmetic shift.] |
sra |
| Verilog In the semiconductor and electronic design industry, Verilog is a hardware description language used to model electronic systems. Verilog HDL, not to be confused with VHDL , is most commonly used in the design, verification, and implementation of digital logic chips at the register-transfer level...
|
<<< |
>>>[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.] |
| C C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
/C++C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...
/GoGo is a compiled, garbage-collected, concurrent programming language developed by Google Inc.The initial design of Go was started in September 2007 by Robert Griesemer, Rob Pike, and Ken Thompson. Go was officially announced in November 2009. In May 2010, Rob Pike publicly stated that Go was being...
(signed types only)[The >> operator in C and C++ is not necessarily an arithmetic shift for signed integers. The C99]C99 is a modern dialect of the C programming language. It extends the previous version with new linguistic and library features, and helps implementations make better use of available computer hardware and compiler technology.-History:...
standard specifies that the resulting value is implementation-defined for a right shift in which the left operand is a signed integer that is negative. However, most implementations use sign extension, thereby making the >> operator an arithmetic shift. For instance, the GCC is such an implementation. |
<< |
>> |
| Java Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...
, JavaScriptJavaScript is a prototype-based scripting language that is dynamic, weakly typed and has first-class functions. It is a multi-paradigm language, supporting object-oriented, imperative, and functional programming styles....
, PythonPython is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...
, PHPPHP is a general-purpose server-side scripting language originally designed for web development to produce dynamic web pages. For this purpose, PHP code is embedded into the HTML source document and interpreted by a web server with a PHP processor module, which generates the web page document...
, RubyRuby is a dynamic, reflective, general-purpose object-oriented programming language that combines syntax inspired by Perl with Smalltalk-like features. Ruby originated in Japan during the mid-1990s and was first developed and designed by Yukihiro "Matz" Matsumoto...
, etc. |
<< |
>> |
OpenVMSOpenVMS , previously known as VAX-11/VMS, VAX/VMS or VMS, is a computer server operating system that runs on VAX, Alpha and Itanium-based families of computers. Contrary to what its name suggests, OpenVMS is not open source software; however, the source listings are available for purchase...
macro language |
@[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.)] |
| 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 Common Lisp, commonly abbreviated CL, is a dialect of the Lisp programming language, published in ANSI standard document ANSI INCITS 226-1994 , . From the ANSI Common Lisp standard the Common Lisp HyperSpec has been derived for use with web browsers...
|
ash |
| Ocaml |
lsl |
asr |
| Standard ML Standard ML is a general-purpose, modular, functional programming language with compile-time type checking and type inference. It is popular among compiler writers and programming language researchers, as well as in the development of theorem provers.SML is a modern descendant of the ML...
|
<< |
~>> |
| Haskell Haskell is a standardized, general-purpose purely functional programming language, with non-strict semantics and strong static typing. It is named after logician Haskell Curry. In Haskell, "a function is a first-class citizen" of the programming language. As a functional programming language, the...
|
shiftL |
shiftR |
In
computer programmingComputer programming is the process of designing, writing, testing, debugging, and maintaining the source code of computer programs. This source code is written in one or more programming languages. The purpose of programming is to create a program that performs specific operations or exhibits a...
, an
arithmetic shift is a
shift operatorIn mathematics, and in particular functional analysis, the shift operator or translation operator is an operator that takes a function to its translation . In time series analysis, the shift operator is called the lag operator....
, sometimes known as a
signed shift (though it is not restricted to signed operands). For
binary numberThe binary numeral system, or base-2 number system, represents numeric values using two symbols, 0 and 1. More specifically, the usual base-2 system is a positional notation with a radix of 2...
s it is a
bitwise operationA bitwise operation operates on one or more bit patterns or binary numerals at the level of their individual bits. This is used directly at the digital hardware level as well as in microcode, machine code and certain kinds of high level languages...
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 shiftIn computer science, a logical shift is a bitwise operation 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 the operand is simply moved a given number of bit...
, when shifting to the right, the leftmost bit (usually the
sign bitIn computer science, the sign bit is a bit in a computer numbering format that indicates the sign of a number. In IEEE format, the sign bit is the leftmost bit...
in signed integer representations) is replicated to fill in all the vacant positions (this is a kind of
sign extensionSign extension is the operation, in computer arithmetic, of increasing the number of bits of a binary number while preserving the number's sign and value...
).
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 2
n. Shifting right by
n bits on a
two's complementThe two's complement of a binary number is defined as the value obtained by subtracting the number from a large power of two...
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 setThe x86 instruction set has been extended several times, introducing wider registers and datatypes and/or new functionality.-x86 integer instructions:...
, 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.
History and details
The formal definition of an arithmetic shift, from
Federal Standard 1037CFederal Standard 1037C, titled Telecommunications: Glossary of Telecommunication Terms is a United States Federal Standard, issued by the General Services Administration pursuant to the Federal Property and Administrative Services Act of 1949, as amended....
is that it is:
- A shift, applied to the representation of a number in a fixed radix
In mathematical numeral systems, the base or radix for the simplest case is the number of unique digits, including zero, that a positional numeral system uses to represent numbers. For example, for the decimal system the radix is ten, because it uses the ten digits from 0 through 9.In any numeral...
numeration system and in a fixed-pointIn computing, a fixed-point number representation is a real data type for a number that has a fixed number of digits after the radix 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 shiftIn computer science, a logical shift is a bitwise operation 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 the operand is simply moved a given number of bit...
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 overflowThe term arithmetic overflow or simply overflow has the following meanings.# In a computer, the condition that occurs when a calculation produces a result that is greater in magnitude than that which a given register or storage location can store or represent.# In a computer, the amount by which a...
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
divisionright|thumb|200px|20 \div 4=5In mathematics, especially in elementary arithmetic, division is an arithmetic operation.Specifically, if c times b equals a, written:c \times b = a\,...
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
DECDigital Equipment Corporation was a major American company in the computer industry and a leading vendor of computer systems, software and peripherals from the 1960s to the 1990s...
,
IBMInternational Business Machines Corporation or IBM is an American multinational technology and consulting corporation headquartered in Armonk, New York, United States. IBM manufactures and sells computer hardware and software, and it offers infrastructure, hosting and consulting services in areas...
,
Data GeneralData General was one of the first minicomputer firms from the late 1960s. Three of the four founders were former employees of Digital Equipment Corporation. Their first product, the Data General Nova, was a 16-bit minicomputer...
, and
ANSIThe American National Standards Institute is a private non-profit organization that oversees the development of voluntary consensus standards for products, services, processes, systems, and personnel in the United States. The organization also coordinates U.S. standards with international...
that make such statements. However, as Steele points out, they are all wrong.
Logical right shifts are equivalent to division by a power of the radix
only on "N-1s'-complement" machines (for radix "N"). Logical 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 ones' complement architectures to newer
two's complementThe two's complement of a binary number is defined as the value obtained by subtracting the number from a large power of two...
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 languageC is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
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.
[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 actual behaviour of their target architectures.]
However, the aforementioned discrepancy arises only from the way division is defined on integers: 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 KnuthDonald Ervin Knuth is a computer scientist and Professor Emeritus at Stanford University.He is the author of the seminal multi-volume work The Art of Computer Programming. Knuth has been called the "father" of the analysis of algorithms...
describes this in terms of a
floor functionIn mathematics and computer science, the floor and ceiling functions map a real number to the largest previous or the smallest following integer, respectively...
.