Editing Bitwise operation (section)

==Bit shifts==
<!-- Courtesy note per [[WP:RSECT]]: [[Bit shift]], [[Bit-shift]] and variants redirect here -->
{{redir|Binary shift|the excess-3 code|Shifted binary (code)|the general concept|Offset binary}}
The '''bit shifts''' are sometimes considered bitwise operations, because they treat a value as a series of bits rather than as a numerical quantity. In these operations, the digits are moved, or ''shifted'', to the left or right. [[Processor register|Register]]s in a computer processor have a fixed width, so some bits will be "shifted out" of the register at one end, while the same number of bits are "shifted in" from the other end; the differences between bit shift operators lie in how they determine the values of the shifted-in bits.

===Bit addressing===
If the width of the register (frequently 32 or even 64) is larger than the number of bits (usually 8) of the smallest addressable unit, frequently called byte, the shift operations induce an addressing scheme from the bytes to the bits.
Thereby the orientations "left" and "right" are taken from the standard writing of numbers in a [[place-value notation]], such that a left shift increases and a right shift decreases the value of the number ― if the left digits are read first, this makes up a [[big-endian]] orientation.
Disregarding the boundary effects at both ends of the register, arithmetic and logical shift operations behave the same, and a shift by 8&nbsp;bit positions transports the bit pattern by 1&nbsp;byte position in the following way:
: {|
| [[Little-endian]] ordering:
| a left shift by 8 positions increases the byte address by 1,
|-
|
| a right shift by 8 positions decreases the byte address by 1.
|-
| [[Big-endian]] ordering:
| a left shift by 8 positions decreases the byte address by 1,
|-
|
| a right shift by 8 positions increases the byte address by 1.
|}

===Arithmetic shift===
{{main|Arithmetic shift}}
[[File:Rotate left logically.svg|thumb|150px|Left arithmetic shift]]
[[File:Rotate right arithmetically.svg|thumb|150px|Right arithmetic shift]]
In an ''arithmetic shift'' (sticky shift), the bits that are shifted out of either end are discarded. In a left arithmetic shift, zeros are shifted in on the right; in a right arithmetic shift, the [[sign bit]] (the MSB in two's complement) is shifted in on the left, thus preserving the sign of the operand.

This example uses an 8-bit register, interpreted as two's complement:

    00010111 (decimal +23) LEFT-SHIFT
 =  0010111'''0''' (decimal +46)

    10010111 (decimal −105) RIGHT-SHIFT
 =  '''1'''1001011 (decimal −53)

In the first case, the leftmost digit was shifted past the end of the register, and a new 0 was shifted into the rightmost position. In the second case, the rightmost 1 was shifted out (perhaps into the [[carry flag]]), and a new 1 was copied into the leftmost position, preserving the sign of the number. Multiple shifts are sometimes shortened to a single shift by some number of digits. For example:

    00010111 (decimal +23) LEFT-SHIFT-BY-TWO
 =  010111'''00''' (decimal +92)

A left arithmetic shift by ''n'' is equivalent to multiplying by 2<sup>''n''</sup> (provided the value does not [[arithmetic overflow|overflow]]), while a right arithmetic shift by ''n'' of a [[two's complement]] value is equivalent to taking the [[floor and ceiling functions|floor]] of division by 2<sup>''n''</sup>. If the binary number is treated as [[ones' complement]], then the same right-shift operation results in division by 2<sup>''n''</sup> and [[rounding#Round half towards zero|rounding toward zero]].

===Logical shift===
{{main|Logical shift}}
<!--images placed next to each other as text is currently so short-->
{| style="float:right;"  border="0" cellpadding="0" cellspacing="0"
|-
| [[File:Rotate left logically.svg|thumb|150px|Left logical shift]]
| [[File:Rotate right logically.svg|thumb|150px|Right logical shift]]
|}
In a ''logical shift'' (zero fill shift), zeros are shifted in to replace the discarded bits. Therefore, the logical and arithmetic left-shifts are exactly the same.

However, as the logical right-shift inserts value 0 bits into the most significant bit, instead of copying the sign bit, it is ideal for unsigned binary numbers, while the arithmetic right-shift is ideal for signed [[two's complement]] binary numbers.
{{Clear}}

===Circular shift===
{{further|Circular shift}}
{{anchor|bit rotation}} <!-- Courtesy note per [[WP:RSECT]]: [[Bit rotation]] and [[Bitwise rotation]] link here -->
Another form of shift is the ''circular shift'', ''bitwise rotation'' or ''bit rotation''.

====Rotate====
<!--images placed next to each other as text is currently so short-->
{| style="float:right;"  border="0" cellpadding="0" cellspacing="0"
|-
| [[File:Rotate left.svg|thumb|150px|Left circular shift or rotate]]
| [[File:Rotate right.svg|thumb|150px|Right circular shift or rotate]]
|}
In this operation, sometimes called ''rotate no carry'', the bits are "rotated" as if the left and right ends of the register were joined. The value that is shifted into the right during a left-shift is whatever value was shifted out on the left, and vice versa for a right-shift operation. This is useful if it is necessary to retain all the existing bits, and is frequently used in digital [[cryptography]].{{Clarification needed|reason=In what process in cryptography is it used?|date=August 2020}}
{{Clear}}

====Rotate through carry====
<!--images placed next to each other as text is currently so short-->
{| style="float:right;"  border="0" cellpadding="0" cellspacing="0"
|-
|[[File:Rotate left through carry.svg|thumb|150px|Left rotate through carry]]
|[[File:Rotate right through carry.svg|thumb|150px|Right rotate through carry]]
|}
''Rotate through carry'' is a variant of the rotate operation, where the bit that is shifted in (on either end) is the old value of the carry flag, and the bit that is shifted out (on the other end) becomes the new value of the carry flag.

A single ''rotate through carry'' can simulate a logical or arithmetic shift of one position by setting up the carry flag beforehand. For example, if the carry flag contains 0, then <code>x RIGHT-ROTATE-THROUGH-CARRY-BY-ONE</code> is a logical right-shift, and if the carry flag contains a copy of the sign bit, then <code>x RIGHT-ROTATE-THROUGH-CARRY-BY-ONE</code> is an arithmetic right-shift. For this reason, some microcontrollers such as low end [[PIC microcontroller|PIC]]s just have ''rotate'' and ''rotate through carry'', and don't bother with arithmetic or logical shift instructions.

Rotate through carry is especially useful when performing shifts on numbers larger than the processor's native [[word size]], because if a large number is stored in two registers, the bit that is shifted off one end of the first register must come in at the other end of the second. With rotate-through-carry, that bit is "saved" in the carry flag during the first shift, ready to shift in during the second shift without any extra preparation.
{{Clear}}

=== In high-level languages ===
{{further|Circular shift#Implementing circular shifts}}

==== In C family of languages ====
{{anchor|Shifts in C family of languages}}
In C and C++ languages, the logical shift operators are "<code>&lt;&lt;</code>" for left shift and "<code>&gt;&gt;</code>" for right shift. The number of places to shift is given as the second argument to the operator. For example,

<syntaxhighlight lang="c">x = y << 2;</syntaxhighlight>

assigns <code>x</code> the result of shifting <code>y</code> to the left by two bits, which is equivalent to a multiplication by four.

Shifts can result in implementation-defined behavior or [[undefined behavior]], so care must be taken when using them. The result of shifting by a bit count greater than or equal to the word's size is undefined behavior in C and C++.<ref name=":0" /><ref>{{Cite web|url=http://en.cppreference.com/w/cpp/language/operator_arithmetic#Bitwise_shift_operators|title=Arithmetic operators - cppreference.com|website=en.cppreference.com|access-date=2016-07-06}}</ref> Right-shifting a negative value is implementation-defined and not recommended by good coding practice;<ref>{{cite web|title=INT13-C. Use bitwise operators only on unsigned operands|url=https://www.securecoding.cert.org/confluence/display/c/INT13-C.+Use+bitwise+operators+only+on+unsigned+operands|website=CERT: Secure Coding Standards|publisher=Software Engineering Institute, Carnegie Mellon University|access-date=7 September 2015}}</ref> the result of left-shifting a signed value is undefined if the result cannot be represented in the result type.<ref name=":0">[http://std.dkuug.dk/JTC1/SC22/WG14/www/docs/n843.htm JTC1/SC22/WG14 N843 "C programming language"], section 6.5.7</ref>

In C#, the right-shift is an arithmetic shift when the first operand is an int or long. If the first operand is of type uint or ulong, the right-shift is a logical shift.<ref>{{cite web|url=http://msdn.microsoft.com/en-us/library/xt18et0d%28v=vs.110%29.aspx|title=Operator (C# Reference)|access-date=14 July 2013|publisher=Microsoft}}</ref>

=====Circular shifts=====
{{anchor|Circular shifts in C-family languages}}
The C-family of languages lack a rotate operator (although C++20 provides <code>std::rotl</code> and <code>std::rotr</code>), but one can be synthesized from the shift operators. Care must be taken to ensure the statement is well formed to avoid [[undefined behavior]] and [[timing attack]]s in software with security requirements.<ref name="StackOverflow">{{cite web|url=https://stackoverflow.com/q/31387778|title=Near constant time rotate that does not violate the standards?|access-date=12 August 2015|publisher=Stack Exchange Network}}</ref> For example, a naive implementation that left-rotates a 32-bit unsigned value <code>x</code> by <code>n</code> positions is simply
<syntaxhighlight lang="c">
uint32_t x = ..., n = ...;
uint32_t y = (x << n) | (x >> (32 - n));
</syntaxhighlight>

However, a shift by <code>0</code> bits results in undefined behavior in the right-hand expression <code>(x >> (32 - n))</code> because <code>32 - 0</code> is <code>32</code>, and <code>32</code> is outside the range 0–31 inclusive. A second try might result in
<syntaxhighlight lang="c">
uint32_t x = ..., n = ...;
uint32_t y = n ? (x << n) | (x >> (32 - n)) : x;
</syntaxhighlight>
where the shift amount is tested to ensure that it does not introduce undefined behavior. However, the branch adds an additional code path and presents an opportunity for timing analysis and attack, which is often not acceptable in high-integrity software.<ref name="StackOverflow" /> In addition, the code compiles to multiple machine instructions, which is often less efficient than the processor's native instruction.

To avoid the undefined behavior and branches under [[GNU Compiler Collection|GCC]] and [[Clang]], the following is recommended. The pattern is recognized by many compilers, and the compiler will emit a single rotate instruction:<ref>{{cite web|url=https://gcc.gnu.org/bugzilla/show_bug.cgi?id=57157|title=Poor optimization of portable rotate idiom|access-date=11 August 2015|publisher=GNU GCC Project}}</ref><ref>{{cite web|url=https://software.intel.com/en-us/forums/topic/580884|title=Circular rotate that does not violate C/C++ standard?|access-date=12 August 2015|publisher=Intel Developer Forums}}</ref><ref name=LLVM>{{cite web|url=https://llvm.org/bugs/show_bug.cgi?id=24226|title=Constant not propagated into inline assembly, results in &quot;constraint 'I' expects an integer constant expression&quot;|access-date=11 August 2015|publisher=LLVM Project}}</ref>
<syntaxhighlight lang="c">
uint32_t x = ..., n = ...;
uint32_t y = (x << n) | (x >> (-n & 31));
</syntaxhighlight>

There are also compiler-specific [[Intrinsic function|intrinsics]] implementing [[circular shift]]s, like [http://msdn.microsoft.com/en-us/library/t5e2f3sc(VS.80).aspx _rotl8, _rotl16], [http://msdn.microsoft.com/en-us/library/yy0728bz(VS.80).aspx _rotr8, _rotr16] in Microsoft [[Visual C++]]. Clang provides some rotate intrinsics for Microsoft compatibility that suffers the problems above.<ref name=LLVM /> GCC does not offer rotate intrinsics. Intel also provides x86 [https://software.intel.com/sites/landingpage/IntrinsicsGuide/#text=rot&techs=Other intrinsics].

==== Java ====
{{anchor|Shifts in Java}}
In [[Java (programming language)|Java]], all integer types are signed, so the "<code>&lt;&lt;</code>" and "<code>&gt;&gt;</code>" operators perform arithmetic shifts. Java adds the operator "<code>&gt;&gt;&gt;</code>" to perform logical right shifts, but since the logical and arithmetic left-shift operations are identical for signed integer, there is no "<code>&lt;&lt;&lt;</code>" operator in Java.

More details of Java shift operators:<ref>The Java Language Specification, section [http://docs.oracle.com/javase/specs/jls/se7/html/jls-15.html#jls-15.19 15.19. Shift Operators]</ref>
* The operators <code><<</code> (left shift), <code>>></code> (signed right shift), and <code>>>></code> (unsigned right shift) are called the ''shift operators''.
* The type of the shift expression is the promoted type of the left-hand operand. For example, <code>aByte >>> 2</code> is equivalent to {{code|2=java|((int) aByte) >>> 2}}.
* If the promoted type of the left-hand operand is int, only the five lowest-order bits of the right-hand operand are used as the shift distance. It is as if the right-hand operand were subjected to a bitwise logical AND operator & with the mask value 0x1f (0b11111).<ref name="jls15.22.1">{{cite web|url=http://docs.oracle.com/javase/specs/jls/se7/html/jls-15.html#jls-15.22.1|title=Chapter 15. Expressions|website=oracle.com}}</ref> The shift distance actually used is therefore always in the range 0 to 31, inclusive.
* If the promoted type of the left-hand operand is long, then only the six lowest-order bits of the right-hand operand are used as the shift distance. It is as if the right-hand operand were subjected to a bitwise logical AND operator & with the mask value 0x3f (0b111111).<ref name="jls15.22.1"/> The shift distance actually used is therefore always in the range 0 to 63, inclusive.
* The value of {{code|n >>> s}} is ''n'' right-shifted ''s'' bit positions with zero-extension.
* In bit and shift operations, the type <code>''byte''</code> is implicitly converted to <code>''int''</code>. If the byte value is negative, the highest bit is one, then ones are used to fill up the extra bytes in the int. So {{code|1=byte b1 = -5; int i = b1 {{!}} 0x0200;|2=java}} will result in {{code|1=i == -5}}.

==== JavaScript ====
{{anchor|Shifts in JavaScript}}
[[JavaScript]] uses bitwise operations to evaluate each of two or more [[units place]] to 1 or 0.<ref>[https://www.w3schools.com/js/js_bitwise.asp "JavaScript Bitwise"]. ''W3Schools.com''.</ref>

==== Pascal ====
{{anchor|Shifts in Pascal}}
In Pascal, as well as in all its dialects (such as [[Object Pascal]] and [[GNU Pascal|Standard Pascal]]), the logical left and right shift operators are "<code>shl</code>" and "<code>shr</code>", respectively. Even for signed integers, <code>shr</code> behaves like a logical shift, and does not copy the sign bit. The number of places to shift is given as the second argument. For example, the following assigns ''x'' the result of shifting ''y'' to the left by two bits:

 <syntaxhighlight lang="pascal">x := y shl 2;</syntaxhighlight>