Archimedean group

2012-01-05T07:04:19Z

98.248.229.177: /* Definition */

{{refimprove|date=August 2010}}

In [[digital computer]] [[computer programming|programming]], a '''bitwise operation''' operates on one or more [[bit pattern]]s or [[Binary numeral system|binary numerals]] at the level of their individual [[bit]]s. It is a fast, primitive action directly supported by the [[central processing unit|processor]], and is used to manipulate values for comparisons and calculations.

On simple low-cost processors, typically, bitwise operations are substantially faster than division, several times faster than multiplication, and sometimes significantly faster than addition. While modern processors usually perform addition and multiplication just as fast as bitwise operations due to their longer [[instruction pipeline]]s and other [[computer architecture|architectural]] design choices, bitwise operations do commonly use less power because of the reduced use of resources.

==Bitwise operators==
In the explanations below, any indication of a bit's position is counted from the right (least significant) side, advancing left. For example, the binary value 0001 (decimal 1) has zeroes at every position but the first one.

===NOT===

The '''bitwise NOT''', or '''complement''', is a [[unary operation]] that performs [[negation|logical negation]] on each bit, forming the [[ones' complement]] of the given binary value. Bits that are 0 become 1, and those that are 1 become 0. For example:

NOT 0111 (decimal 7)
= 1000 (decimal 8)

The bitwise complement is equal to the [[two's complement]] of the value minus one. If two's complement arithmetic is used, then

:NOT ''x'' = −''x'' − 1.

For unsigned [[Integer_(computer_science)|integers]], the bitwise complement of a number is the "mirror reflection" of the number across the half-way point of the unsigned integer's range. For example, for 8-bit unsigned integers, <code>NOT x = 255 - x</code>, which can be visualized on a graph as a downward line that effectively "flips" an increasing range from 0 to 255, to a decreasing range from 255 to 0. A simple but illustrative example use is to invert a grayscale image where each pixel is stored as an unsigned integer.

===AND===
A '''bitwise AND''' takes two binary representations of equal length and performs the [[Logical conjunction|logical AND]] operation on each pair of corresponding bits. The result in each position is 1 if the first bit is 1 ''and'' the second bit is 1; otherwise, the result is 0. In this, we perform the multiplication of two bits; i.e., 1 × 0 = 0 and 1 × 1 = 1. For example:

0101 (decimal 5)
AND 0011 (decimal 3)
= 0001 (decimal 1)

The operation may be used to determine whether a particular bit is ''set'' (1) or ''clear'' (0). For example, given a bit pattern 0011 (decimal 3), to determine whether the second bit is set we use a bitwise AND with a bit pattern containing 1 only in the second bit:

0011 (decimal 3)
AND 0010 (decimal 2)
= 0010 (decimal 2)

Because the result 0010 is non-zero, we know the second bit in the original pattern was set. This is often called ''bit masking''. (By analogy, the use of [[masking tape]] covers, or ''masks'', portions that should not be altered or portions that are not of interest. In this case, the 0 values mask the bits that are not of interest.)

If we store the result, this may be used to clear selected bits in a register. Given the example 0110 (decimal 6), the second bit may be cleared by using a bitwise AND with the pattern that has a zero only in the second bit:

0110 (decimal 6)
AND 1101 (decimal 13)
= 0100 (decimal 4)

Because of this property, it becomes easy to check the parity of a binary number by checking the value of the lowest valued bit. Using the example above:

0110 (decimal 6)
AND 0001 (decimal 1)
= 0000 (decimal 0)

Therefore 6 is divisible by two and even.

===OR===
A '''bitwise OR''' takes two bit patterns of equal length and performs the [[Logical disjunction|logical inclusive OR]] operation on each pair of corresponding bits. The result in each position is 1 if the first bit is 1 ''or'' the second bit is 1 ''or'' both bits are 1; otherwise, the result is 0. For example:

0101 (decimal 5)
OR 0011 (decimal 3)
= 0111 (decimal 7)

The bitwise OR may be used to set selected bits, such as a specific bit (or [[Flag word|flag]]) in a register where each bit represents an individual [[Boolean data type|Boolean]] state. For example 0010 (decimal 2) can be considered a set of four flags, where the first, third, and fourth flags are clear (0) and the second flag is set (1). The fourth flag may be set by performing a bitwise OR between this value and a bit pattern with only the fourth bit set:

0010 (decimal 2)
OR 1000 (decimal 8)
= 1010 (decimal 10)

This technique is an efficient way to store a number of Boolean values using as little memory as possible.

===XOR===
A '''bitwise XOR''' takes two bit patterns of equal length and performs the [[Exclusive disjunction|logical exclusive OR]] operation on each pair of corresponding bits. The result in each position is 1 if only the first bit is 1 ''or'' only the second bit is 1, but will be 0 if both are 0 or both are 1. In this we perform the comparison of two bits, being 1 if the two bits are different, and 0 if they are the same. For example:

0101 (decimal 5)
XOR 0011 (decimal 3)
= 0110 (decimal 6)

The bitwise XOR may be used to invert selected bits in a register (also called [[toggle]] or flip). Any bit may be toggled by XORing it with 1. For example, given the bit pattern 0010 (decimal 2) the second and fourth bits may be toggled by a bitwise XOR with a bit pattern containing 1 in the second and fourth positions:

0010 (decimal 2)
XOR 1010 (decimal 10)
= 1000 (decimal 8)

This technique may be used to manipulate bit patterns representing sets of Boolean states.

[[Assembly language]] programmers sometimes use XOR as a short-cut to setting the value of a [[Processor register|register]] to zero. Performing XOR on a value against itself always yields zero, and on many architectures this operation requires fewer clock cycles and/or memory than loading a zero value and saving it to the register.

===Mathematical equivalents===

Assuming {{mvar|x > y}}, for the non-negative integers, the bitwise operations can be written as follows:

<math>\text{NOT }x = \sum_{n=0}^{b}2^n\left[\left(\left\lfloor\frac{x}{2^n}\right\rfloor \bmod 2 + 1\right) \bmod 2\right]</math>

<math>x\text{ AND }y = \sum_{n=0}^{b}2^n\left(\left\lfloor\frac{x}{2^n}\right\rfloor \bmod 2\right)\left(\left\lfloor\frac{y}{2^n}\right\rfloor \bmod 2\right)</math>

<math>x\text{ OR }y = \sum_{n=0}^{b}2^n\left[\left[\left(\left\lfloor\frac{x}{2^n}\right\rfloor \bmod 2\right) + \left(\left\lfloor\frac{y}{2^n}\right\rfloor \bmod 2\right) + \left(\left\lfloor\frac{x}{2^n}\right\rfloor \bmod 2\right)\left(\left\lfloor\frac{y}{2^n}\right\rfloor \bmod 2\right)\bmod 2\right]\bmod 2\right]</math>

<math>x\text{ XOR }y = \sum_{n=0}^{b}2^n\left[\left[\left(\left\lfloor\frac{x}{2^n}\right\rfloor \bmod 2\right) + \left(\left\lfloor\frac{y}{2^n}\right\rfloor \bmod 2\right)\right]\bmod 2\right]</math>

Where <math>b</math> is the number of bits in <math>x</math> (<math>= \lfloor\log_2 x\rfloor</math> for all <math>x \neq 0</math>).

===Atomic inputs===
For the examples above often 3 and 5 (binary 0011 and 0101) are used as inputs. They correspond to the unchanged [[Statement (logic)|statements]] among the [[Binary operation|2-ary]] [[logical connective]]s. For the [[Ternary operation|3-ary]] case 15, 51 and 85 would be used. These numbers are found in the number triangle {{OEIS2C|A211344}}:
1 01
3 5 0011 0101
15 51 85 00001111 00110011 01010101

==Bit shifts==
The '''bit shifts''' are sometimes considered bitwise operations, because they operate on the binary representation of an integer instead of its numerical value; however, the bit shifts do not operate on pairs of corresponding bits, and therefore cannot properly be called ''bit-wise''. 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.

===Arithmetic shift===
{{main|Arithmetic shift}}
[[Image:Rotate left logically.svg|thumb|150px|Left arithmetic shift]]
[[Image:Rotate right arithmetically.svg|thumb|150px|Right arithmetic shift]]
In an ''arithmetic 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]] is shifted in on the left, thus preserving the sign of the operand. Further on, while shifting right, the empty spaces will be filled up with a copy of the most significant bit (MSB), meaning that by shifting the second arithmetic shift register (ASR#2), with a MSB=1, you fill up with 1.

This example uses an 8-bit register:

00010111 (decimal +23) LEFT-SHIFT
= 00101110 (decimal +46)

10010111 (decimal −105) RIGHT-SHIFT
= 11001011 (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
= 01011100 (decimal +92)

A left arithmetic shift by ''n'' is equivalent to multiplying by 2''n'' (provided the value does not [[arithmetic overflow|overflow]]), while a right arithmetic shift by ''n'' of a [[two's complement]] value is equivalent to dividing by 2''n'' and rounding toward [[negative infinity]]. If the binary number is treated as [[ones' complement]], then the same right-shift operation results in division by 2''n'' and rounding toward zero.

===Logical shift===
{{main|Logical shift}}

{| align=right border=0 cellpadding=0 cellspacing=0
| [[Image:Rotate left logically.svg|thumb|150px|Left logical shift]]
| [[Image:Rotate right logically.svg|thumb|150px|Right logical shift]]
|}
In a ''logical 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.
 

===Rotate no carry===
{{main|Circular shift}}

{| align=right border=0 cellpadding=0 cellspacing=0
| [[Image:Rotate left.svg|thumb|150px|Left circular shift or rotate]]
| [[Image:Rotate right.svg|thumb|150px|Right circular shift or rotate]]
|}
Another form of shift is the ''circular shift'' or ''bit rotation''. In this operation, the bits are "rotated" as if the left and right ends of the register were joined. The value that is shifted in on the right during a left-shift is whatever value was shifted out on the left, and vice versa. This operation is useful if it is necessary to retain all the existing bits, and is frequently used in digital [[cryptography]].
 

===Rotate through carry===

{| align=right border=0 cellpadding=0 cellspacing=0
|[[Image:Rotate left through carry.svg|thumb|150px|Left rotate through carry]]
|[[Image:Rotate right through carry.svg|thumb|150px|Right rotate through carry]]
|}
''Rotate through carry'' is similar to the ''rotate no carry'' operation, but the two ends of the register are separated by the [[carry flag]]. 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 the 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.
 

===Shifts in C, C++, C#, Python===
In C-inspired languages, the left and right shift operators are "<code><<</code>" and "<code>>></code>", respectively. The number of places to shift is given as the second argument to the shift operators. For example,

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

assigns ''x'' the result of shifting ''y'' to the left by two bits.

In C, the result of right-shifting a negative value is implementation-defined, and the result of left-shifting a signed value is undefined if the result cannot be represented in the result type.<ref>[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)|accessdate=14 July 2013|publisher=Microsoft}}</ref>

There are also compiler-specific 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++]].

===Shifts in Java===
In [[Java (programming language)|Java]], all integer types are signed, and the "<code><<</code>" and "<code>>></code>" operators perform arithmetic shifts. Java adds the operator "<code>>>></code>" to perform logical right shifts, but because the logical and arithmetic left-shift operations are identical, there is no "<code><<<</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>((int) aByte) >>> 2</code>.
* 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">[http://docs.oracle.com/javase/specs/jls/se7/html/jls-15.html#jls-15.22.1 JLS §15.22.1]</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 ''n >>> s'' is ''n'' right-shifted ''s'' bit positions with zero-extension.

===Shifts in Pascal===
In Pascal, as well as in all its dialects (such as [[Object Pascal]] and [[GNU Pascal|Standard Pascal]]), the left and right shift operators are "<code>shl</code>" and "<code>shr</code>", respectively. 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:

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

==Applications==
Bitwise operations are necessary particularly in lower-level programming such as writing device drivers, low-level graphics, communications protocol packet assembly, and decoding.

Although machines often have efficient built-in instructions for performing arithmetic and logical operations, in fact, all these operations can be performed by combining the bitwise operators and zero-testing in various ways.{{Citation needed|date=May 2012}}

For example, here is a [[pseudocode]] example showing how to multiply two arbitrary integers <code>a</code> and <code>b</code> (<code>a</code> greater than <code>b</code>) using only bitshifts and addition:

<code>
c = 0
'''while''' b ≠ 0
'''if''' (b '''and''' 1) ≠ 0
c = c + a
left shift a by 1
right shift b by 1

'''return''' c
</code>

NB: In this code <code>=</code> is the assignment operator, not the equality operator. 
This implementation of [[ancient Egyptian multiplication]], like most [[multiplication algorithm]]s, involves bitshifts. In turn, even addition can be written using just bitshifts and zero-testing{{Citation needed|date=May 2012}}:

<code>
'''while''' a ≠ 0
c = b '''and''' a
b = b '''xor''' a
left shift c by 1
a = c

'''return''' b
</code>

NB: In this code <code>=</code> is the assignment operator, not the equality operator.

==See also==
*[[Bit manipulation]]
*[[Bitboard]]
*[[Bitwise operations in C]]
*[[Boolean algebra (logic)]]
*[[Double dabble]]
*[[Find first set]]
*[[Karnaugh map]]
*[[Logic gate]]
*[[Logical operator]]

==References==
<references />

==External links==
*[http://www.miniwebtool.com/bitwise-calculator/ Online Bitwise Calculator] supports Bitwise AND, OR and XOR
*[http://www.cs.uiowa.edu/~jones/bcd/divide.html Division using bitshifts]
* "[http://demonstrations.wolfram.com/BitwiseOperationsModN/ Bitwise Operations Mod N]" by Enrique Zeleny, [[Wolfram Demonstrations Project]].
* "[http://demonstrations.wolfram.com/PlotsOfCompositionsOfBitwiseOperations/ Plots Of Compositions Of Bitwise Operations]" by Enrique Zeleny, The Wolfram Demonstrations Project.

{{DEFAULTSORT:Bitwise Operation}}
[[Category:Binary arithmetic]]
[[Category:Operators (programming)]]
[[Category:Articles with example pseudocode]]
[[Category:Boolean algebra]]

formulasearchengine - User contributions [en]

Archimedean group