Bitwise operations

Operations in C++ (and supposedly any other programming language) are of various types. They can be categorized into:

1. Arithmetic Operations (Like +, -, *, /, %)
   
2. Comparison Operations (Like ==, <, <=, >, >=, != Also logical operations like &&, ||, !)
   
3. Bitwise Operations (Like &, |, ^, ~, <<, >>)
   
4. Others (Like =, [], (), new, delete and some others)
   

As expected bitwise operations are used to perform operations on bits or binary numbers. For example the >> and << shifts the binary number to right or left. This is similar to multiplication and division by powers of 2 but is, in fact, faster.

The &, |, ^ perform a bitwise "and", "or" and "xor". Given 2 binary numbers (110101, 1010110) the result of the "and" operation will be:
0110101
1010110
0010100
the result of the "or" operations will be:
0110101
1010110
1110111
the result of the "xor" operation will be:
0110101
1010110
1100011
the result of the "not" operation will be:
0110101
1001010
(performing "not" on the first binary number)

The most common use of bitwise operations in problems will be in Dynamic Programming problems, or to be more general in the representation of a 1 dimensional boolean array with size less than or equal to 32 into one single integer. This representation is possible since the 2 values any element in the boolean array can have is either 0 or 1. If we put together these 0s and 1s corresponding to the values of the array elements we get a binary number (with less than or equal to 32 bits). It's also possible to reverse this operation, having one single integer less than or equal to 2^32 - 1, we can represent it as a 1 dimensional boolean array with size less than or equal to 32. Of course the array size is determined according to the size of the data type being used. If we use long long (64 bits) we can have up to 64 as the size of the array.

Some other bitwise operations can be of a great help in different situations. An xor operation saved me once from Time Limit Exceeded (and gave me Wrong Answer which I fixed later :D). Xor can also be used in xor swap algorithm, the symmetric difference and the xor linked list.

Here's a small program that performs the above operations. I may add the xor linked list some other time.