Bits & Bitmasking
Bit-masking often referred to as Bit-Magic by many, is not that scary as people think it is.
I’ve observed my colleagues complaining about getting repeated TLE’S (Time Limit Exceeded) and Space Complexity issues while running their codes. So this is where Bit-Magic comes to rescue.
In this two part series I’ll sharing my present knowledge about bit-masking and how it helps to optimize algorithms (reason why it is also known as Bit-Magic).
This part will deliver the basic intuition behind bit-masking and how to manipulate different bits and in the next part I’ll be discussing some advanced problems which can be solved and optimized using bit-masking along with dynamic programming.
Through this article I’ll be discussing the following:
· Bits and Bit-masking: An Intro.
· Bitwise operators.
· Hands-on Bit-Masking.
Onto the article!!
Bits and Bit-masking: An Intro.
A bit is a single Boolean value (0 or 1), small set(s) of which makes a bit-mask. A bit is said to be set if and only if it is ‘1’. For eg: in 10011, 1st, 2nd and 5th bits are set while 3rd and 4th are not.
‘Mask’ in bit-mask can be understood as a way to hide/show some information. Let’s take a basic example to understand it more thoroughly. Assume we have a set of 5 characters {‘a’ , ‘b’, ‘c’, ‘d’, ‘e’} and we want to make different strings from them. Here we’ll create a mask of 5 bits ( _ _ _ _ _ ) where each bit will tell us if we are refereeing to that character or not. In simple words 10011 will represent string equivalent to “ade”, 00000 will represent an empty string, 11111 will refer to “abcde” and so on
Having understood what bits and bit-masks are, it is the perfect time to dive into some operations which can be used to manipulate bits.
Bitwise Operators
AND operator (&) : Given two bit-masks, ‘&’ operator will give 1 whenever both bits are set.
OR operator (|): Given two bit-masks, ‘|’ operator will give 1 whenever either of two bits are set.
XOR operator (^): Given two bit-masks, ‘^’ operator will give 1 whenever both the bits are different.
An important observation here is that XOR of any two same numbers will always be 0, and XOR of any number with 0 is the number itself.
Can you think of some situations where this concept can be applied ??
If you did , woahh !! you are going good. If not, don’t worry we’ll discuss the same in the later part of the article.
Shift Operators:
How to set the kth bit of a number ?
A simple approach to this problem is to first create a mask such that kth bit is set in it.
We can achieve this by shifting 1 k times to left or by doing (1<<k).
Eg: We have to set 3 bit of 1000001. 1<< 3 will give us 1000.
Now in order to set the 3rd bit ( or kth bit) we only need to perform OR operation of number and mask.
Therefore 1000001 | 1000 = 1001001 (having 3rd bit set)
Code :
N = N | (1<<k)
How to clear the kth bit ?
If we are given the task of clearing kth bit of number (or setting the kth bit to 0) we can create a mask having all 1’s but kth bit as 0. The advantage that we get from this mask is that, if we perform ‘&’ operation with mask we will get all bits of the number as it is with an added advantage that our kth bit is now 0. Because (0 & any no) is always 0.
Let’s say we have 1001101 and we want to clear it’s 3rd bit. So 1<< 3 will give us 1000 but we want something like 1110111. What can we do ??
Let’s try out by taking negation of our mask. So ~(mask) = ~(1000) = ~(0001000) = 1110111
Now we can simply perform ‘&’ operation of number & mask to clear the 3rd bit.
Having learnt about bitwise operators and how to access a particular bit by creating masks, here is a simple problem for you as an exercise.
Q You are given a number of n bits. Set all the bits between k and l to 1. Take k and l from the user. (k < l <= n)
Play with these operators to have a better grip on bit-wise operations.
Now it’s time to learn how bit-making can be used to optimize the code. Let’s jump onto it !!
Hands-on Bit-Masking:
We all know that information is stored in the form of bits in computer memory, which means directly manipulating these bits will yield faster results than performing computation on ordinary data.
Okay, so we’ll now see by solving some question how bit-masking actually optimizes the code.
Q Let’s start with a simple example of swapping two number.
Eg: a = 4 (100 in binary), b = 6 (110 in binary)
We want a = 6 and b = 4 as our answer.
a = a ^ b (a = 4 ^ 6)
b = a ^ b (b = 4 ^ 6 ^ 6) {and we’ve seen earlier that xor of same numbers is 0, hence b = 4 (since 6 ^ 6= 0) }
a = a ^ b (a = 4 ^ 6 ^ 4= 6)
Hence a = 6 and b = 4.
We successfully achieved our task..yayy!!
This can obviously be achieved by normal swapping but using bitwise operators will lead to a more time efficient code.
Q Given a list of integers where all integers occur even times, expect one which occur odd times. Find out that integer.
Eg: l = { 1,2,2,1,1,4,4,4,5,4,5} our ans. should be 1
A simple brute force approach would say to count the number of times each integer is present in the list, and print the integer corresponding to odd count. In the worst case it will lead to a time complexity of O(n*k) where k is the number of distinct elements.
Let’s try out this using bit-masking. What happens if we take xor of all the elements ?
Taking xor will cancel out all those numbers which are occurring even times (recall that XOR of same numbers = 0) and we are only left with the integer which is repeating odd times. Intresting !! Isn’t it ??
I hope you are getting a better grip on it now!! Let’s discuss a little complex problem now.
Q Given a string , print all it’s permutations.
Eg: Given string is “abc”. So, very first thought that will strike us is how we can access every character of the string. Remember about mask that we learnt ?? Yes, you got it right!! Here, we will create a mask for every possible state and once every character is visited we’ll print our answer. Length of the mask will obviously be equal to the length of the string.
At every iteration we’ll be checking which all bits which are not set and then try different permutations by setting different bits in every iteration. If a particular bit is already set then we need not do anything, but if it isn’t then we’ve to try all possible combinations. Different states of mask will decide what next combination is going to be.
This part will become more clear as we head on to the coding section for this problem.
Here is the code for the same:
I hope now you have a clear understanding of how bit-masking (or I would say bit-magic) works.
Now it’s time to get your hands dirty by practicing on some interesting problems.
My next article on bit-masking will focus on more complex problems involving Bit-masking along with Dynamic Programming.
Till then Happy Coding :)
Links to some interesting problems:
· https://practice.geeksforgeeks.org/problems/subsets-with-xor-value/0
