When it comes to problem-solving during interview preparations or competitive programming there are many instances where we encounter errors like Time Limit Exceeds (TLE). These errors are mostly due to the fact that our solution does not run in stipulated time limit and it crosses the allotted time limit.
To counter this problem, there are many algorithms available and Bit Manipulation is one of them. Bit manipulations are fast and can be used in optimizing time complexity. You would be thinking what is the use of Bit manipulation if we have other algorithms/ways to solve the problems.
Consider a problem- XOR of Sum of all possible pairs of an array
A naive approach is to run two loops consider each pair and then find the sum of each pair and then calculate XOR of all the sums.
In this case, time complexity- O(n2)
An optimized approach is based on the XOR operation. We know that the XOR of the two same numbers is Zero. So pairs like (a,b), (b, a), (a, c), (c, a) will have the same sum and hence their XOR will be Zero. so we need to consider pairs like (a, a), (b, b), (c, c) and hence XOR of the sum of pairs will be XOR of all elements of the array multiplied by 2.
In this case, time complexity is O(n)
We will discuss the above problem in detail in upcoming article.
Bit manipulation in detail
Now let us understand bit manipulations in detail.
Bit Manipulations is nothing but an act of applying logical operations on bits to achieve the desired result.
Since implementing bit manipulation involves logical operations, so let’s start our discussion with logical operators and their respective operations.
Logical operations are any set of operations which involves manipulating bits using some operators and such operator are known as Logical Bitwise Operators.
|A||B||A & B||A | B||A ^ B||~ (A)|
So far we have basic understanding of bit-wise operators and respective operations. Now we will be diving deep into bit manipulation concepts.
Important bit manipulation tricks for problem solving
1. Left Shift
In left shift each bit is being shifted by k bit(s) towards left and consequently most significant bit (MSB) is discarded.
- 2 << 1 = 4
- 2 << 2 = 8
- 2 << 3 = 16
Did you observed some pattern in above examples?
Yes, here’s a trick. Observe carefully and you will get that 2 << 1 = 2 * power(2, 1) , 2 << 2 = 2 * power(2, 2) and so on.
If there is a number N and we have to perform left shift by i bits, then N = N * power(2, i)
2. Right Shift
In right shift each bit is being shifted by k bit(s) towards right and consequently least significant bit (LSB) is discarded.
Let’s have a look at some more examples
- 8>> 1 = 4
- 8 >> 2 = 2
- 8 >> 3 = 1
Did you observed some pattern in above examples?
Yes, here’s a trick. Observe carefully and you will get that 8 >> 1 = 2 / (power(2, 1)) , 8 >> 2 = 8 / (power(2, 2)) and so on.Conclusion : If there is a number N and we have to perform right shift by i bits, then N = N / ( power(2, i)
3. Swapping two numbers
Suppose a=2 and b=3, then we need a=3 and b=2, so swapping will be done as-
def swapping(a,b): a=a^b b=a^b a=a^b print(a,b) def main(): a=int(input()) b=int(input()) swapping(a,b) if __name__=="__main__": main()
4. To check whether number is even or ODD
Let’s observe some even and odd numbers and their respective binary representations-
2 = 0010 3 = 0011 4 = 1000 9 = 1001 10 = 1010
Upon carefully observing the binary representations of above numbers you will find that if a number is even then LSB is 0 else LSB is 1.
Now observe one more thing-
2 & 1 => 0010 & 0011 = 0000 3 & 1 => 0011 & 0001 = 0001 9 & 1 => 1001 & 0001 = 0001 4 & 1 => 0100 & 0001 = 0000
Bitwise AND of N with 1 is 0 for even numbers and is 1 for odd numbers.
def oddeven(N): if(N&1==0): print("EVEN") else: print("ODD") def main(): N=int(input()) oddeven(N) if __name__=="__main__": main()
5. How to set a bit in a number N
If we want to set a bit at kth position then-
- Left shift 1 k times (let p=1<<k)
- Find bitwise OR of N with p i.e. answer=N|p
Consider and example-
N=8 (1000) suppose we want to set 2nd bit means k=2 since 1 = 0001 (in binary) Therefore, p=1<<k
p=0100 (in binary)
Hence, N | p = 1000 | 0100 = 1100 (equivalent to 35 in decimal)
def setKthBit(N,k): p=1<<k answer=N|p return answer def main(): N,k=map(int,input().split()) print(setKthBit(N,k)) if __name__=="__main__": main()
6. How to unset a bit in a number N
If we want to unset a bit at kth position then-
- Left shift 1 k times (Let p=1<<k)
- Negate p => ~p
- Find bitwise AND of N with ~p , it will unset the required bit.
Suppose N=51 and k=4 N = 110011 then, p = 1 << 4 = 010000 So, ~p = 101111
Therefore N & ~p = 100011 (equivalent to 35 in decimal)
def setKthBit(N,k): p=1<<k answer=N & ~p return answer def main(): N,k=map(int,input().split()) print(setKthBit(N,k)) if __name__=="__main__": main()
So far we have learned some basic but useful concepts in bit manipulation.In the Second Part of Bit Manipulation series I will be covering some important concepts with tips and tricks like-
- Check if kth bit is set.
- Count Number of set bits.
- Toggle a bit at kth position.
- Check if a number is divisible by 3
- Swap all odd and even bits
- Binary to gray code conversion