Editing Bitwise operation (section)

== Boolean algebra ==
{{Main|Boolean algebra}}
Sometimes it is useful to simplify complex expressions made up of bitwise operations, for example when writing compilers. The goal of a compiler is to translate a [[high-level programming language]] into the most efficient [[machine code]] possible. Boolean algebra is used to simplify complex bitwise expressions.

=== AND ===

* <code>x & y = y & x</code>
* <code>x & (y & z) = (x & y) & z</code>
* <code>x & 0xFFFF = x</code><ref name=":1">Throughout this article, 0xFFFF means that all the bits in your data type need to be set to 1. The exact number of bits depends on the width of the data type.</ref>
* <code>x & 0 = 0</code>

* <code>x & x = x</code>

=== OR ===

* <code>x | y = y | x</code>
* <code>x | (y | z) = (x | y) | z</code>
* <code>x | 0 = x</code>
* <code>x | 0xFFFF = 0xFFFF</code>
* <code>x | x = x</code>

=== NOT ===

* <code>~(~x) = x</code>

=== XOR ===

* <code>x ^ y = y ^ x</code>
* <code>x ^ (y ^ z) = (x ^ y) ^ z</code>
* <code>x ^ 0 = x</code>
* <code>x ^ y ^ y = x</code>
* <code>x ^ x = 0</code>
* <code>x ^ 0xFFFF = ~x</code>

Additionally, XOR can be composed using the 3 basic operations (AND, OR, NOT)

* <code>a ^ b = (a | b) & (~a | ~b)</code>
* <code>a ^ b = (a & ~b) | (~a & b)</code>

=== Others ===

* <code>x | (x & y) = x</code>
* <code>x & (x | y) = x</code>
* <code>~(x | y) = ~x & ~y</code>
* <code>~(x & y) = ~x | ~y</code>
* <code>x | (y & z) = (x | y) & (x | z)</code>
* <code>x & (y | z) = (x & y) | (x & z)</code>
* <code>x & (y ^ z) = (x & y) ^ (x & z)</code>
* <code>x + y = (x ^ y) + ((x & y) << 1)</code>
* <code>x - y = ~(~x + y)</code>

=== Inverses and solving equations ===
It can be hard to solve for variables in Boolean algebra, because unlike regular algebra, several operations do not have inverses. Operations without inverses lose some of the original data bits when they are performed, and it is not possible to recover this missing information.

* Has inverse
** NOT
** XOR
** Rotate left
** Rotate right
* No inverse
** AND
** OR
** Shift left
** Shift right

=== Order of operations ===
{{Main article|Operators in C and C++#Operator precedence}}
Operations at the top of this list are executed first. See the main article for a more complete list.

* <code>( )</code>
* <code>~ -</code><ref>- is negation here, not subtraction</ref>
* <code>* / %</code>
* <code>+ -</code><ref>- is subtraction here, not negation</ref>
* <code><< >></code>
* <code>&</code>
* <code>^</code>
* <code>|</code>