---
# System prepended metadata

title: Bit Manipulation

---

# Bit Manipulation
---
Bitwise operators

`&`: and (only true if input bits are ture)
`|`: or (only ture if any input bits is true)
`^`: xor (True if one nad only one input bit is true)
`>>`: Right shift 
`<<`: Left shift
`~`: not (flips the input bit)
`<<` Left Shift

`<<` Left Shift
* Shifts the binary digits by n, pads 0's on the right. 
* Left shift is equivalent to multiplying the bit pattern with 2 power k( if we are shifting k bits ).
```

1 << 1 = 2 = 21
1 << 2 = 4 = 22 1 << 3 = 8 = 23
1 << 4 = 16 = 24
…
1 << n = 2n

example:
22: 00010110
<<
2:  00000010
88: 10110000
```

`>>` Right Shift
* Shifts the binary digits byn, pads 0's on the left.
* Each shift is a divide by 2 with round towards negative infinity.
* Right shift is equivalent to dividing the bit pattern with 2k ( if we are shifting k bits ).
```
4 >> 1 = 2
6 >> 1 = 3
5 >> 1 = 2
16 >> 4 = 1

Example:
22: 00010110
<<
2:  00000010
5:  00000101
```
`>>` and `<<` are primarly used for bit masking. 


#### SET BIT

```python=
def set_bit(x, position):
    mask = 1 << position
    return x | mask
```

x:    00000110
mask: 00100000

return: 


#### Clearing BIT

```python=
def clear_bit(x, position):
    mask = 1 << position
    return x & ~mask
```

x:    00000110
position: 00000010
mask:  00000100
~mask: 11111011 

return: 00000010


#### Flip BIT

```python=
def flip_bit(x, position):
    mask = 1 << position
    return x ^ mask
```

x 01100110
position 00000010
mask 00000100

reutrn 01100010

#### IS BIT SET

Is a given bit at a certain postion is SET(is 1).


```python=
def is_bit_set(x, position):
    shifted = x >> position
    return shifted & 1
```

#### MODIFY BIT
```python=
def modify_bit(x, position, state):
    """
    state is param that tells us to set a bit 
    or clear a bit
    """
    mask = 1 << position
    return (x & ~mask) | (-state & mask)
```

#### BIT TRICKS 

##### To check if the number is even
* `&` ANDing the number with 1 gives 0 or 1 
 -- `0` if it's even 
 -- `1` if it's odd 
```python=
x = "Any int number here"
(x & 1) == 0
```

> [Practice Question](https://leetcode.com/problems/number-of-steps-to-reduce-a-number-to-zero/) 

##### To check if the number is a power of two
* If a number is x binary representation of (x-1) can be obtained by simply flipping all the bits to the right of rightmost 1 in x and also including the rightmost 1. 
```bash
Let, x = 4 = (100)2
x - 1 = 3 = (011)2
Let, x = 6 = (110)2
x - 1 = 5 = (101)2
```
* x & (x-1) will have all the bits equal to the x except for the rightmost 1 in x. In the given example below the values enclosed in `||` are the same for both the x and x-1 if `x` is not the power of 2. 
* If the number is neither zero nor a power of two, it will have 1 in more than one place.
```bash
Let, x = 6 = 1|1|0
(x- 1) = 5 = 1|0|1

Let,x = 16 = |1|0000
(x-1) = 15 = |0|1111

Let,x = 8 = |1|000
(x-1) = 7 = |0|111

Let,x = 23 = 1011|1|
(x-1) = 22 = 1011|0|
```

```python=
x = "Any int number here"
(x & x-1) == 0
```

##### XOR
* XOR of a number with itself is 0
```python=
x = "Any int number"
(x ^ x) == 0
```

* XOR of a number with 0 is number itself.
```python=
(x ^ 0) == 0
```

* Ordering in XOR does not matter, both will give the same output.
```python=
output = (7 ^ 3) ^ (5 ^ 4 ^ 5) ^ (3 ^ 4)
output = 7 ^ (3 ^ (5 ^ 4 ^ 5)) ^ (3 ^ 4)
```

```python=
"""
Write a function to count the number of bits 
that are diffrent between two numbers.
"""
```

---
[Refrence](https://www.hackerearth.com/practice/basic-programming/bit-manipulation/basics-of-bit-manipulation/tutorial/)