## Fun with Bits

I recently stumbled across a very *peculiar* topic called **Bit Manipulation**. In most of my programming days, I haven't actually relied on the binary operation to get me the result, I know under the hood everything is converted into `0`

's and `1`

's but it was all abstraction to me.

The case was different here. While working with Bit Manipulation, I had to actually rely on arithmetic bit operations to get me to the result. So it became real interesting real soon.

### Bitwise operators

Basic operation done on bits are done with **bitwise operators**. Since we primarily work on bits these operations are fast and are optimized to reduce time complexity.

The first three `&`

, `|`

and `~`

are fairly straightforward. So I would briefly go over it.

`&`

: if both bits are of equal size than `&`

operator would compare each position and would return True/1 if input bits are True/1. Similarly for False/0.

```
6 : 1 1 0
5 : 1 0 1
-------- &
1 0 0
```

`|`

: if both bits are of equal size than `&`

operator would compare each position and would return True/1 if input bits differ. Similarly for False/0.

```
5 : 1 0 0
3 : 0 1 1
-------- |
1 1 1
```

`~`

: Not operator just compliments the bit it gets. In *fancy* computer lingo it gives one’s complement of a number.

```
5 : 1 0 1
-------- ~
0 1 0
```

Now coming to more interesting operators:

Operator | Name |
---|---|

`^` |
XOR |

`>>` |
Right Shift |

`<<` |
Left Shift |

##### XOR

If two bits are of two equal-size `^`

of both bits in the compared position would be 1 if compared bits are of different binary and would be 0 if bot the compared bits are the same.

```
6 : 1 1 0
5 : 1 0 1
-------- ^
0 1 1
```

XOR of a number with itself is 0

`x = "Any int number" (x ^ x) == 0`

XOR of a number with 0 is number itself.

`(x ^ 0) == 0`

Ordering in XOR does not matter, both will give the same output.

`output = (7 ^ 3) ^ (5 ^ 4 ^ 5) ^ (3 ^ 4) output = 7 ^ (3 ^ (5 ^ 4 ^ 5)) ^ (3 ^ 4)`

While discussing Left Shift,<< and Right Shift, >> we will be talking about arithmetic shifts.

#### 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 = 1 * (2 ** 1)
1 << 2 = 4 = 1 *(2 ** 2)
1 << 3 = 8 = 1 * (2 ** 3)
1 << 4 = 16 = 1* (2 ** 4)
…
1 << n = 2n
```

#### Right shift `>>`

- Shifts the binary digits by n, pads 0's on the left.
- 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
```

Both Right shift and Left shift operators come real handy in **masking**.

Masking allows the user to check/change a particular bit at a particular position.

Some of the common functions associated with masking are:

##### Set Bit

- The set bit method is generally used to
*SET*a particular with`1`

. - To achieve this we would need to create a mask at the particular position where we want to
*SET* - The mask can be created with the help of the
`<<`

if the left shift operator.

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

- In the above code snippet we are SETing the bit at 0th index.

```
masking = 1 << 0 = 1 * (2 ** 0)
6 : 1 1 0
1 << 0 : 0 0 1
-------- |
1 1 1
```

##### IS BIT SET

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

##### Clearing Bit

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

##### Flip Bit

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

##### Modify Bit

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

#### Observations

Bit manipulation can be used to solve problems that you are familiar with but necessarily don't know about. Here are some of my observations that I noted while using *bit manipulation*.

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

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

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

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

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

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

There are a lot more things that can be done with just bits and are definitely not limited to the above observations. Try to find your own observations. Happy coding!