# Bitwise operators

Bitwise operations allow you to manipulate data at a binary level. Remember that all data is represented by binary numbers under the hood.
For example, the binary representation of the decimal number `5` is `0101`.

## What are Binary Numbers?

We can derive the decimal version of a binary number by summing each bit's position as the exponent of `2`, where position `0` is the right-most bit, or the least significant bit.
So `0101` = (0 * 23) + (1 * 22) + (0 * 21) + (1 * 20) = 0 + 4 + 0 + 1 = `5`

## Bitwise AND: &

The bitwise AND (&) of two numbers is a comparison of each bit in the same position of the input numbers, and is 1 only if both bits in that position are 1.

ABA & B
000
010
100
111

## Bitwise OR: |

The bitwise OR (&) of two numbers is 1 in corresponding bit positions if either bit is 1, and 0 if both bits are 0.

### OR Truth Table

`A``B``A | B`
000
011
101
111

## Bitwise XOR: ^

The bitwise XOR (^), or exclusive or of two numbers is 1 in corresponding bit positions only if the bits differ. Otherwise the output is 0.

ABA ^ B
000
011
101
110

### XOR Tricks

The XOR operation has some neat properties that make it useful for solving some coding interview problems.
1. XOR operations are commutative, which means the ordering of the operations do not matter: `a ^ b ^ c = c ^ a ^ b`
2. A number XOR with itself is always 0: `a ^ a = 0`.
3. A number XOR with 0 is the number itself: `a ^ 0 = a`.
For example, let's consider the problem of finding the missing number in a given array of numbers `1..n`, but is missing one number from that range.
One way to find the missing number is to use all 3 XOR properties above and do the following:
1. XOR every number in the input array
2. XOR the result with each number from the range `1..n`.
3. The remaining number is the missing number.

## Bitwise Complement: ~

The bitwise Complement (~) flips all the bits of the single input number.

### Twos complement numbers

To support signed integers, Python uses twos complement numbers.
Twos complement numbers implies that For numbers greater than or equal to 0 are represented by its regular binary representation ( `3 = 0011`).
Negative numbers are represented with the most significant bit set to `1`.
For example, to get the binary representation of `-14`, working with an 8-bit integer:
1. Start with the absolute value of the input: `14`, or in binary form `0000 1110`.
2. Flip each bit - 1 becomes 0, and 0 becomes 1: `1111 0001`
3. Add 1 to that `1111 0010`
So twos complement binary numbers can represent both positive and negative numbers.
Remember, in twos complement binary numbers, one bit is occupied to determine the sign of the number, so an 8-bit integer can really only hold 7 bits of information.
So the max value a signed 8-bit integer can hold is `127`.

## Bitwise Left Shift: <<

A bitwise left shift takes a binary number and literally shifts all the bits to the left, and adds a 0 in the least significant bit positions.
For example:
`0101 << 1 = 1010 # same as 5 << 1 = 5 * 2 = 100001 << 3 = 1000 # same as 1 << 3 = 1 * 8 = 8`
Let's say the shift amount is `X`. You can see that left shifts are the same as multiplying an input number by 2X

### Bit Shifting tricks

Shifting along with the AND operation can be used to create a bit mask, which is a way to extract specific bits from a number.
For example, shifting 1 to the second digit, and applying a bitwise AND to the bit mask and a number would extract the second bit of the input number.

## Bitwise Right Shift: >>

A bitwise right shift takes a binary number and shifts all the bits to the right by a specified amount, and adds a 0 in the most significant bit positions.
For example:
`1000 >> 2 = 0010 # same as 8 >> 2 = 8 / 4 = 20101 >> 1 = 1010 # same as 5 >> 1 = 5 / 2 = 2`
Again, let's say the shift amount is `X`. You can see that right shifts are the same as dividing an input number by 2X
Note that the division of odd numbers by any factor of 2 results in some remainder. This is essentially lost in a bitwise right shift.
Therefore, bitwise right shifts actually apply floor division to a number.

## 6 Essential Primitives Coding Interview Problems

Master Primitives by trying the coding challenges below.
1. 1.Swap bitsEasy
2. 2.Power of twoEasy
3. 3.Count bitsMedium
4. 4.Reverse bitsMedium
5. 5.Find duplicateMedium