Hello and welcome to a wonderful series of competitive programming with python. In some of our previous blogs, we have covered two important topics as Recursion and Backtracking. And in a data structure point of view, we have covered popular array algorithms and important coding problems that you need to know. from this article, we are heading forward and starting a new topic as Bit Manipulation. If any of the topics is remaining to complete then please I would like to request you to complete it fast because it will help you build a good base and move forward step by step with a good RoadMap that we are following.
Table of Contents
Introduction to Bit Manipulation
We all know that machines capture and store the information in form of numbers by converting each number in byte form or binary representation (either 0 or 1). So each number in a binary representation of a certain number is known as a bit. If a bit is 1 then it is known as set bit and if a bit is 0 then it is known as unset bit. The binary representation of a number starts from 0 and after this as we add 1 at the back so the series goes on. 1+1 forms a 10 where 1 goes in carrying and 0 is written. And 1+0 forms a 1. The binary representation from the number 1 to 10 series is shown below.
Now there are many different coding problems that require a lot of computation in a loop but can easily be solved using bit manipulation by converting a decimal into binary and applying some bitwise operators. let's study all bitwise operators first.
Important Bitwise Operators
There are various bitwise operators that we should know and what kind of operations they perform in order to use them in programming. I hope that you are familiar with bitwise operators because you might have read them in school or college in form of logic Gates or used them in programming like And, Or, Not operator.
1) AND (&) - And is like multiplication. When we have 0 and 1 then the result is always 0. It gives 1 only when both the bits are true.
For example X = 5 (101) and Y = 3 (011)
X & Y = (101) & (011) = 001 = 1
2) OR (|) - Or is like Addition. When we have at least one bit as 1 then the result will always be 1. Only when both the bits are zero the result will be zero.
3) NOT (~) - It is used to toggle the bits or to find the complement of bits. It simply changes 0 to 1 and 1 to 0.
4) XOR (^) - It is also known as exclusive OR. The result of XOR is 1 if the corresponding bits of both the operands are different. If both bits are the same then the result is 0.
5) Left shift (<<) - Left shift operator shifts all the bits towards the left by a certain number of specified bits. To calculate the result of the left-shift operator by K bits use the formula (2**K). For example, we have 5 and left shift by 1 means k is 1 so 1<<k which is equal to 2^1 and the answer is 2(010).
6) Right Shift operator (>>) - It seems to be the opposite of the left-shift operator but this is not the case. It is used for a different kind of computation. The formula you can use here is by dividing the x with (2**K). For example N = 5 and k = 2 so the right shift of N = N>>K) is (5 / 2**2) is equivalent to 5 / 4.
Important Bit Manipulation Algorithms | Bit Hacks to know
Now we are familiar with bitwise operations and how they are used. Now the question that arises is where we can use these operators to optimize the code and run efficiently so now we will pick the top patterns where Bit manipulation really helps us to solve in second.
1) Check If a number is the power of two
Given a number N and you need to find whether the number is the power of 2 or not. The basic method you will apply is you will run a loop in square root times of number and check for the two power. So this method is not sufficient to pass all the test cases all the time.
Now Note that the number is the power of two if its binary representation has only one set bit. So, think of a binary representation of N-1 that will have all the bits the same as N except the rightmost bit. The binary representation of N-1 can simply be obtained from the binary representation of N by flipping the bits to the right of the rightmost set bit including the rightmost set bit itself.
👉 So If N has only one set bit then N & (N-1) must equal to zero. Let's take an example.
In the above example, since the rightmost set bit and a bit to the right of it were flipped and bitwise and will make all the bit zero. Now let us build its program. We apply the Not because if it is a power of two then the answer will be 0 so in If the statement applying Not will give us 1.
def isPowerOfTwo(num):
return not(num & (num-1))
print(isPowerOfTwo(4))
👊 NOTE ~ The same approach can be used to check the number of even or odd. If the last bit of binary representation of a number is 0 then it is even else it is odd.
2) Check If Kth bit is set or unset
Given a number and task is to check that the Kth bit in a binary representation of a given number is Set (1) or unset(0). The naive approach that most of them will follow is first to convert decimal to binary and then convert the binary representation into string form and through indexing check that it is set or unset.
When we have a bitwise operator that can directly return the Kth bit then we do not need to do this many calculations. Do the bitwise And of number with the left shift of k with 1. It will return a positive number if the Kth bit is 1 otherwise False.
Example - Let us understand with an example how bitwise and left shift operators can help us.
💻 Code - Now you can easily implement the function.
def checkKBit(num, k):
if (num & (1 << k)):
return True
else:
return False
print(checkKBit(5, 2)) #True
3) Count the number of 1s in the binary representation of a number
Given a positive integer, your task is to return the total number of 1 (set bits) present in a binary representation of a number. The simple approach is to convert decimal to binary and using loop counts the number of 1s in binary representation that cost O(log N) time complexity.
However, we can make the solution efficient to run in a number of ones present in a binary representation of a number. Let us discuss the Algorithm. So, What we can do in we can apply a loop till the number is greater than zero. Update the number by finding its bitwise And between number and number-1. It will flip the rightmost set bit and the bits after the rightmost set bit. So every time a rightmost set bit is unset and helps us count the number of 1s in a binary representation of a number.
Example ~ Let us take the example and solve it using the discussed approach
👉 The above algorithm is also known as Brian Kernighan's Algorithm. So, let us now write the code for Kernighan's algorithm.
def count1s(num):
cnt = 0
while num > 0:
num = (num & (num - 1))
cnt = cnt + 1
return cnt
print(count1s(5))
4) Generate All possible subsets of a set
We have done this question in our Recursion tutorial but the complexity of using recursion is more than the bit manipulation. We know that the number of subsets of a set N is equal to 2^N. So the binary sequence of length N will represent values from range 0 to 2^N-1 which is equal to a number of subsets of the set.
All the bits in the binary sequence denote the elements present from the set, thus representing the subset. In simple words find the binary representation from 0 to 2^N-1 and wherever set bit is present include that position element in a subset and in that way we are able to generate 2^N-1 subsets of a set.
👉Example
💻Code - Now let's build the algorithm.
def generateSubsets(arr, n):
all_subsets = []
#iterate from 0 to 2^N-1 to generate all Subsets
for i in range(0, 2**n):
'''
for each i representing subset check
bits are set in binary representation os i
'''
curr_subset = []
for j in range(0, n):
#If jth bit in binary representation of i is set.
if (i & (1 << j)):
curr_subset.append(arr[j])
if curr_subset:
all_subsets.append(curr_subset)
return all_subsets
arr = [10, 20, 30]
ans = generateSubsets(arr, 3)
print(ans)
Application of Bitwise operations in Computer Programming
- Bitwise operations in heavily used in the compression, and encryption of data. It is used in Communication models to transfer packets.
- They are used in networking where data reduction is required So, booleans are packed together.
- Bitwise operators are prominent in embedded systems, control systems, etc where memory loss or data leakage is still an issue.
- It is also useful in GUI programming because most GUI depends on high complex operations to highlight something where XOR is used.
End Notes
Bitwise operators are very important in any programming language and help to reduce the time complexity of the program and perform efficient calculations. Bit Manipulation is one most important topics in competitive programming and technical interviews because at least there is one question based on the array and simple numbers where converting decimal to binary and then by use of bitwise operators help solve problems in a very efficient way. In this article we have looped over the basic and important bit hacks that you should know from an interview point of view. Now from the next article we will pick some top coding problems and understand the bit manipulation approach to solve them and learn how to identify problems and apply bit manipulation.
If you have any doubts or queries then feel free to post them in the comment section below 👇, and can connect and send your queries through the contact form.
Thank you for your time! 😊