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