# 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 * 2**=^{3}) + (1 * 2^{2}) + (0 * 2^{1}) + (1 * 2^{0}) = 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.

### AND Truth Table

A | B | A & B |
---|---|---|

0 | 0 | 0 |

0 | 1 | 0 |

1 | 0 | 0 |

1 | 1 | 1 |

### Bitwise AND in Python

## 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` |
---|---|---|

0 | 0 | 0 |

0 | 1 | 1 |

1 | 0 | 1 |

1 | 1 | 1 |

### Bitwise OR in Python

## 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.### XOR Truth Table

A | B | A ^ B |
---|---|---|

0 | 0 | 0 |

0 | 1 | 1 |

1 | 0 | 1 |

1 | 1 | 0 |

### XOR Tricks

The XOR operation has some neat properties that make it useful for solving some coding interview problems.

- XOR operations are
**commutative**, which means the ordering of the operations do not matter:`a ^ b ^ c = c ^ a ^ b`

- A number XOR with itself is always 0:
`a ^ a = 0`

. - 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:

- XOR every number in the input array
- XOR the result with each number from the range
`1..n`

. - The remaining number is the missing number.

### XOR operations in Python

## Bitwise Complement: ~

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

### Bitwise Complement in Python

### 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:- Start with the absolute value of the input:
`14`

, or in binary form`0000 1110`

. - Flip each bit - 1 becomes 0, and 0 becomes 1:
`1111 0001`

- 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 **2**^{X}### 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.

### Left shifts in Python

## 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**2**^{X}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.### Right shifts in Python

## 6 Essential Primitives Coding Interview Problems

Master Primitives by trying the coding challenges below.

- 1.Swap bitsEasy
- 2.Power of twoEasy
- 3.Count bitsMedium
- 4.Reverse bitsMedium
- 5.Find duplicateMedium
- 6.Bitwise additionHard