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

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):
``````
##### Flip Bit
``````def flip_bit(x, position):
``````
##### Modify Bit
``````def modify_bit(x, position, state):
"""
state is param that tells us to set a bit
or clear a bit
"""
``````

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

Practice Question

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