Bitwise operation

Bitwise operators

AND (&): returns a 1 in each bit position for which the corresponding bits of both operands are 1.
0 & 0 = 0
1 & 0 = 0
0 & 1 = 0
1 & 1 = 1

OR (|): returns a 1 in each bit position for which the corresponding bits of either or both operands are 1.
0 | 0 = 0
1 | 0 = 1
0 | 1 = 1
1 | 1 = 1

XOR (^): returns a 1 in each bit position for which the corresponding bits of either but not both operands are 1.
It reads Exclusive OR.
0 ^ 0 = 0
1 ^ 0 = 1
0 ^ 1 = 1
1 ^ 1 = 0

NOT (~): inverts the bits of its operand.
~0 = 1
~1 = 0

Two's Complement

Two's complement is used to represent negative numbers.

Two's complement can be obtained from the following procedure.
1. Flip the binary.
2. Add 1.

In the case of a 4-bit integer (decimal range is min: -8.. max: 7),  two's complement of 0101 is 1011.
1. Flip the binary. 0101 -> 1010
2. Add 1. 1010 -> 1011

The good thing about using two's complement is subtraction can be calculated via addition.
0101 (+5) + 1011 (-5) =  0000 (0)

Bit shifts

Left shift (<<): shifts the specified number of bits to the left.
Excess bits shifted off to the left are discarded.
Zero bits are shifted in from the right.
x = y << z
x is y * (2 ** z).

Right shift (>>): shifts the specified number of bits to the right.
Excess bits shifted off to the right are discarded, and copies of the leftmost bit are shifted in from the left.
x = y >> z
x is y * (2 ** -z).

Watch out for the right shift
https://www.interviewcake.com/concept/java/bit-shift

There are two types of right shifts which are an arithmetic shift and a logical shift.
For Java, there are explicit operators to distinguish those two types.
For some languages, there is no explicit operator and we need to make sure how it works.

With the arithmetic right shift, the least-significant bit is lost and the most-significant bit is copied.
1011 >> 1 // 1101
1011 >> 3 // 1111

With the logical right shift, the least-significant bit is lost and a 0 is inserted on the other end.
1011 >>> 1 // 0101

Some Tricks

Check if even
(x & 1) == 0

Check if the power of two
(x & x-1) == 0