Editing Bitwise operation (section)

==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 (i.e., the rightmost) one.

===NOT===
<!-- linked from redirects [[Bitwise complement]], [[Bit complement]], [[Bitwise NOT]] -->

{{See also|Ones' complement}}

The '''bitwise NOT''', or '''bitwise complement''', is a [[unary operation]] that performs [[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 '''0'''111  (decimal 7)
   = '''1'''000  (decimal 8)

 NOT 10101011  (decimal 171)
   = 01010100  (decimal 84)

The result is equal to the [[two's complement]] of the value minus one. If two's complement arithmetic is used, then <code>NOT x = -x − 1</code>.

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===
[[File:0...15 AND.svg|thumb|Bitwise AND of [[4-bit computing|4-bit]] integers]]
A '''bitwise AND''' is a [[binary operation]] that takes two equal-length binary representations and performs the [[logical AND]] operation on each pair of the corresponding bits. Thus, if both bits in the compared position are 1, the bit in the resulting binary representation is 1 (1&nbsp;× 1&nbsp;= 1); otherwise, the result is 0 (1&nbsp;× 0&nbsp;= 0 and 0&nbsp;× 0&nbsp;= 0). For example:

     010'''1''' (decimal 5)
 AND 001'''1''' (decimal 3)
   = 000'''1''' (decimal 1)

The operation may be used to determine whether a particular bit is ''set'' (1) or ''cleared'' (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:

     00'''1'''1 (decimal 3)
 AND 00'''1'''0 (decimal 2)
   = 00'''1'''0 (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.)

The bitwise AND may be used to clear selected bits (or [[Flag word|flags]]) of a [[Processor register|register]] in which each bit represents an individual [[Boolean data type|Boolean state]]. This technique is an efficient way to store a number of Boolean values using as little memory as possible.

For example, 0110 (decimal 6) can be considered a set of four flags numbered from right to left, where the first and fourth flags are clear (0), and the second and third flags are set (1). The third flag may be cleared by using a bitwise AND with the pattern that has a zero only in the third bit:

     0'''1'''10 (decimal 6)
 AND 1'''0'''11 (decimal 11)
   = 0'''0'''10 (decimal 2)

Because of this property, it becomes easy to check the [[Parity (mathematics)|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)

Because 6 AND 1 is zero, 6 is divisible by two and therefore even.

===OR===
[[File:0...15 OR.svg|thumb|Bitwise OR of 4-bit integers]]
A '''bitwise OR''' is a [[binary operation]] that 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 0 if both bits are 0, while otherwise the result is 1. For example:

    0'''101''' (decimal 5)
 OR 0'''011''' (decimal 3)
  = 0'''111''' (decimal 7)

The bitwise OR may be used to set to 1 the selected bits of the register described above. For example, the fourth bit of 0010 (decimal 2) may be set by performing a bitwise OR with the pattern with only the fourth bit set:

    '''0'''0'''1'''0 (decimal 2)
 OR '''1'''0'''0'''0 (decimal 8)
  = '''1'''0'''1'''0 (decimal 10)

===XOR===
[[File:Z2^4; Cayley table; binary.svg|thumb|Bitwise XOR of 4-bit integers]]
A '''bitwise XOR''' is a [[binary operation]] that 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 one of the bits 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:

     0'''10'''1 (decimal 5)
 XOR 0'''01'''1 (decimal 3)
   = 0'''11'''0 (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:

     '''0'''0'''1'''0 (decimal 2)
 XOR '''1'''0'''1'''0 (decimal 10)
   = '''1'''0'''0'''0 (decimal 8)

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

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

If the set of bit strings of fixed length ''n'' (i.e. [[Word (computer architecture)|machine words]]) is thought of as an ''n''-dimensional [[vector space]] <math>{\bf F}_2^n</math> over the [[Field (mathematics)|field]] [[GF(2)|<math>{\bf F}_2</math>]], then vector addition corresponds to the bitwise XOR.

===Mathematical equivalents===

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

:<math>\begin{align}
   \operatorname{NOT}x &= \sum_{n=0}^{\lfloor\log_2(x)\rfloor} 2^n\left[\left(\left\lfloor\frac{x}{2^n}\right\rfloor \bmod 2 + 1\right) \bmod 2\right] = \sum_{n=0}^{\lfloor\log_2(x)\rfloor} \left[2^{\left\lfloor\log_2(x)\right\rfloor + 1} - 1 - x \right]
\\
  x\operatorname{AND}y &= \sum_{n=0}^{\lfloor\log_2(x)\rfloor} 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)
\\
   x\operatorname{OR}y &= \sum_{n=0}^{\lfloor\log_2(x)\rfloor} 2^n\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)\right)
\\
  x\operatorname{XOR}y &=
    \sum_{n=0}^{\lfloor\log_2(x)\rfloor} 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) =
    \sum_{n=0}^{\lfloor\log_2(x)\rfloor} 2^n\left[\left(\left\lfloor\frac{x}{2^n}\right\rfloor + \left\lfloor\frac{y}{2^n}\right\rfloor\right) \bmod 2\right]
\end{align}</math>

=== Truth table for all binary logical operators ===
There are 16 possible [[truth function]]s of two [[binary variable]]s; this defines a [[truth table]].

Here is the bitwise equivalent operations of two bits P and Q:

{| class="wikitable" style="margin:1em auto 1em auto; text-align:center;"
|-
! ''p'' !! ''q''
| rowspan=5 style="border-bottom:none" |
! [[Contradiction|F]]<sup>0</sup>
! [[Logical NOR|NOR]]<sup>1</sup>
! [[Converse nonimplication|Xq]]<sup>2</sup>
! [[Negation|'''¬p''']]<sup>3</sup>
! [[Material nonimplication|↛]]<sup>4</sup>
! [[Negation|'''¬q''']]<sup>5</sup>
! [[XOR]]<sup>6</sup>
! [[Logical NAND|NAND]]<sup>7</sup>
| rowspan=5 style="border-bottom:none" |
! [[Logical conjunction|AND]]<sup>8</sup>
! [[Logical biconditional|XNOR]]<sup>9</sup>
! [[Projection function|q]]<sup>10</sup>
! [[Material conditional|If/then]]<sup>11</sup>
! [[Projection function|p]]<sup>12</sup>
! [[Converse implication|Then/if]]<sup>13</sup>
! [[Logical disjunction|OR]]<sup>14</sup>
! [[Tautology (logic)|T]]<sup>15</sup>
|-
! 1 !! 1
| 0 || 0 || 0 || 0 || 0 || 0 || 0 || 0 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1
|-
! 1 !! 0
| 0 || 0 || 0 || 0 || 1 || 1 || 1 || 1 || 0 || 0 || 0 || 0 || 1 || 1 || 1 || 1
|-
! 0 !! 1
| 0 || 0 || 1 || 1 || 0 || 0 || 1 || 1 || 0 || 0 || 1 || 1 || 0 || 0 || 1 || 1
|-
! 0 !! 0
| 0 || 1 || 0 || 1 || 0 || 1 || 0 || 1 || 0 || 1 || 0 || 1 || 0 || 1 || 0 || 1
|-
! colspan="2" | Bitwise <br/>equivalents
| style="border-top:none" |
! <small>0</small>
! <small>NOT <br/>(p OR q)</small>
! <small>(NOT p) <br/>AND q</small>
! <small>NOT <br/>p</small>
! <small>p AND <br/>(NOT q)</small>
! <small>NOT <br/>q</small>
! <small>p XOR q</small>
! <small>NOT <br/>(p AND q)</small>
| style="border-top:none" |
! <small>p AND q</small>
! <small>NOT <br/>(p XOR q)</small>
! <small>q</small>
! <small>(NOT p) <br/>OR q</small>
! <small>p</small>
! <small>p OR <br/>(NOT q)</small>
! <small>p OR q</small>
! <small>1</small>
|}