View source for Bitwise Operators

[[Category:Encyclopedia]]
As the name implies, bitwise operators look at the individual bits of a number. Computers store everything in binary, therefore bitwise operations can be used on all types of data, whether the source code displays the data in binary or not. The computer will look at those numbers' binary representations to calculate the result.

==AND==
Bitwise <code>AND</code>, often abbreviated to <code>&</code>, compares each individual bit of two different numbers, and outputs a 1 if they are both 1, and 0 otherwise.
<pre>
    10101101
AND 00110010
------------
    00100000
</pre>

A few properties of <code>AND</code> that aren't readily apparent.
For all numbers A:

* <code>A & 0 = 0</code>
* <code>A & A = A</code>
* <code>A & -1 = A (remember that -1 = FF)</code>
* Every 4 binary digits of A and B can be <code>AND</code>ed separately and concatenated, and the result is the same.
For example, <code>0x37 & 0x49 = ((0x30 & 0x40) | (0x07 & 0x09))</code>
===Filtering===
<code>AND</code> is useful for filtering out unwanted bits for a comparison. A practical example is checking whether a number is odd or even. This uses the property that the least significant bit of all even numbers is 0, and all odd numbers is 1.
<lang C>if ((foo & 1) == 0)
{
   // your code for what happens when foo is even goes here
}
else
{
   // your code for what happens when foo is odd goes here
}</lang>

Filtering is also useful for checking the status of a flag variable, where each bit represents a different options setting. This example is for [[6502 Assembly]].
<lang 6502asm>FLAG_SCROLL equ %10000000 ;0 = no scrolling, 1 = scrolling enabled. 
                          ; This label represents a constant so that we don't have to remember what the flags mean.

LDA statusFlags  ;get the variable statusFlags, an 8 bit value where each bit controls a different aspect of our program.
AND #FLAG_SCROLL ;AND statusFlags with the binary value 0b10000000 (decimal 128)
BNE ScrollScreen ;the corresponding bit of statusFlags was set, so allow the screen to scroll.</lang>

===Random Chance===
Given the output of a random number generator with all equally likely outcomes, you can use <code>AND</code> with that output to create random occurrences. If <math>n</math> is a power of 2, then to create a random event with probability <math>1/n</math>, you just need to <code>AND</code> the RNG output with <math>n-1</math>. In the example below, <code>rand</code> is a randomly generated number. Its size doesn't change the probabilities listed below.

<lang C>
if ((rand & 3) == 0)
{
   //1 in 4 chance of occurring
}
else
{
   //3 in 4 chance of occurring
}

if ((rand & 15) == 0)
{
   //1 in 16 chance of occurring
}
else
{
   //15 in 16 chance of occurring
}</lang>

==OR==
Bitwise <code>OR</code>, often abbreviated to <code>|</code> (SHIFT+\), compares each individual bit of two different numbers, and outputs a 0 if both are 0, and a 1 otherwise.
<pre>
    10101101
OR  00110010
------------
    10111111
</pre>

When we say "or" in the English language, we usually mean "one or the other, but not both." This isn't the case in programming. That's actually a different operator which will be covered later.

A few properties of OR that aren't readily apparent.
For all numbers A:
* <code>A | 0 = A</code>
* <code>A | A = A</code>
* <code>A | -1 = -1</code>


The first property implies that if a subset of a byte is a sequence of zeroes, then <code>OR</code>ing that sequence of zeroes with any bit combination will result in the same bit combination. For example:
<pre>
%11 000 111 | %00 101 000 = %11 101 111
%11 000 111 | %00 111 000 = %11 111 111
%11 000 111 | %00 001 000 = %11 001 111
</pre>
etc.

===Failsafes===
Bits that get <code>OR</code>ed with 1 always equal 1, regardless of their original value. If you have a variable that you want to guarantee at least certain bits are set, you can OR them with those bits. The nice thing about this method is that the actual value of that variable need not be compared to anything. Those bits will get set either way.

===Combining two values without addition===
If you have two values in separate "nibbles", e.g. <code>0xFF00</code> and <code>0x00DD</code>, then an <code>OR</code> of these two will combine them, e.g. <code>0xFFDD</code>. This is just an extension of the property that <code>A | 0 = A</code>.

==XOR==
eXclusive OR, often abbreviated to <code>XOR</code>, <code>^</code> or called <code>EOR</code> in some languages, compares each individual bit of two different numbers, and outputs a 1 if they are different and 0 if they are the same.
<pre>
     10101101
XOR  00110010
------------
     10011111
</pre>

A few properties about <code>XOR</code> that aren't readily apparent:
* If <code>A XOR B = C</code>, then <code>A XOR C = B</code> and <code>B XOR C = A</code>.
* A bit <code>XOR</code>'d with 1 will flip. A bit <code>XOR</code>'d with zero won't change.
* A bitwise <code>NOT</code> is the same as <code>XOR -1</code>.
* <code>A ^ A = 0</code>. Furthermore, if <code>A ^ B = 0</code>, then <code>A = B</code>.
* If <code>((A ^ B) & C) = 0</code>, then A and B both share the bits of C in common.



===Toggling===
A flag register <code>XOR</code>'d with a given value will flip those particular bits, and leave the rest alone.

==NOT==
A bitwise <code>NOT</code>, or <code>~</code> takes one number as an argument and flips all its bits. This has its uses, especially when reading video game controllers, but is a little more limited than the others.

Among <code>AND</code>, <code>OR</code>, <code>XOR</code>, and <code>NOT</code>, only <code>XOR</code> and <code>NOT</code> are reversible.


==Citations==
#[[http://www.6502.org/tutorials/compare_beyond.html Beyond 8-Bit Unsigned Comparisons by Bruce Clark]]