Bit Masking

Hello guys, welcome back to “code with asharam”. If you have read my other posts today, then, you probably know that I have started my YouTube channel for tutorials related to competitive programming. So, please support it like you have supported my blog. In this post, I am going to introduce you to “basics of Bit Masking“. Today, I will not solve any specific problem. This part is just to introduce you to concept of Bit Masking. Before moving ahead with bit masking, let’s discuss the basic concepts of bit manipulation.

Bit Manipulation

Most of you are familiar with the term “Bit”. So, Bit is short for “Binary digit”. When we say we are dealing with Bit, it means that we are dealing with binary digits, i.e., 1 and 0. Binary digits follows the analogy with Boolean algebra in the sense that “1” represents true and “0” represents false. All those operations we can perform on Boolean are also applicable on binary digits. Let’s see how?

  1. AND (&)
    As you know that ‘&’ operation returns true if and only if both the operands are true. Otherwise it returns false. If we apply ‘&’ on binary digits, then, only 1 & 1 will return 1 and 0 will be returned in all the cases.

    8 is 1000 and 9 is 1001 in binary representation
    ==> 8 & 9 = 1000 & 1001 = 1000 = 8
  2. OR (|)
    ‘|’ returns true if at least one of the operands is true which means that it returns false when both the operands are false. So, except for 0 | 0, ‘|’ on any other operand pair will return 1.

     ==> 8 | 9 = 1000 | 1001 = 1001 = 9
  3. NOT (!)
    ‘!’ is applied on single operand and it return true if applied on false and false if applied on true.

    ==> !8 = !(1000) = 0111 = 7
  4. XOR (^)
    ‘^’ return true if exactly one of the operand is true. Hence, both 1^1 and 0^0 will return 0.

    ==> 8 ^ 9 = 1000 ^ 1001 = 0001 = 1

Beyond these 4, we can also perform following 2 operations on integers in binary representation. Note that you cannot use these operations on Booleans.

  1. Left Shift Operator (a << b)
    When applied on integer a, it will append a ‘0s’ in the end of binary representation of that integer. It is equivalent to multiplying a by 2b.

    3 << 1 = 11 << 1 = 110 = 6
    8 << 2 = 1000 << 2 = 100000 = 32
  2. Right Shift Operator (a >> b)
    It will remove b rightmost bits from the integer a. It is equivalent to dividing a by 2b.

    3 >> 1 = 11 >> 1 = 1
    8 >> 2 = 1000 >> 2 = 10 = 2

Let’s see how we can use bit manipulation to make our work little bit easier and these applications will also be widely used in Bit Masking.

Application of Bit Manipulation

  • Check whether a number is odd or not
    As all of you know that a binary number of form abcd is represented as a*23 + b*22 + c*21 + d in decimal system. Clearly, all the term in binary to decimal expansion sum are even except for d. So, whether a number is even or odd depends upon the rightmost bit. If the rightmost bit is 1, then, the number is odd and otherwise even. Hence, we just need to find the rightmost bit which we can find easily taking ‘&’ of the number with 1.

    x & 1 = 1 if x is odd and 0 if x is even
    8 & 1 = 1000 & 0001 = 0
    9 & 1 = 1001 & 0001 = 0001 = 1
  • Find the ith bit
    To find ith bit is set, we just need to take ‘&’ of that bit with 1. Although we can convert the number to binary and then, can easily find the ith bit but it will take O(log2n) time and we want to do it in O(1) time. We can easily do it as follows:

    If x & (1 << i) = 0 then ith bit is 0 and otherwise 1
    2nd bit of 9: 9 & (1 << 2) = 1001 & 100 = 0 => 2nd bit is 0
    2nd bit of 15: 15 & (1 << 2)) = 1111 & 100 = 0100 = 4 => 2nd bit is 1

    Note that we are following 0 based bit indexing.

  • Check whether a number is power of 2 or not
    We can do it easily in O(log2n) time but again we are little greedy and want to do it in O(1) time. Let’s observe few things before moving forward:

    A number which is a power of 2 looks like 1000.
    If we subtract one from it, then, it will be 0111.
    Now, if we take '&' of these 2 numbers, then, we will get 0

    We can generalise above result as follows:

    x & (x-1) = 0 if and only if x is power of 2 and x > 0
  • Set the ith bit of a number
    As I have told you that if take ‘|’ of any bit with 1, then, we will get 1. Hence, we can set ith bit by taking its ‘|’ with 1.

    x = x | (1 << i) will set the ith bit of the number
    If we set 2nd bit of 8, then, we will get 1100 = 12
    8 | (1 << 2) = 1000 | 0100 = 1100 = 12
  • Unset the ith bit of a number
    We just have to take ‘&’ of ith bit with 0 and ith bit will become 0. So, if we take ‘&’ of the number of !(1 << i), then, only ith bit will become 0 and other bits will remain same as we are taking ‘&’ of them with 1.

    x = x & !(1 << i) will unset the ith bit of the number
    If we unset 2nd of 12, then, we will get 1000 = 8
    12 & !(1 << 2) = 1100 & 1011 = 1000 = 8
  • Toggle the ith bit of the number
    As you know that 0^1 = 1 and 1^1 = 0. From this we can conclude that if we take ‘^’ of ith bit with 1, then, we will be able to toggle the ith bit of the number.

    x = x ^ (1 << n) will toggle the ith bit of the number
    If we toggle 2nd bit of 8, then, we will get 1100 = 12
    8 ^ (1 << 2) = 1000 ^ 0100 = 1100 = 12

Until now we were just discussing the basics of Bit. Now, it’s time to get into the real deal and the main topic of this tutorial.

Bit Masking

Before telling you what is Bit Masking, let me tell you that it is not an algorithm like merge sort and not any problem solving technique like dynamic programming. It is a way of representing set and allows O(1) removal and addition of elements into set. So, you can say that Bit Mask is a data structure.
As all of you know that integer is just a bunch of binary digits (0 and 1). Now, we can say that ith element of an array is in the set if ith bit of integer is set (1). Similarly, it is not in the set if ith bit of integer is unset (0). In this way, we can use integers to represent set. And we have already discussed that setting and unsetting bits in an integers takes O(1) time and hence, we can add and remove elements from the set in O(1) time. But there is a limitation to Bit Masking. Since Integers are mostly 32 or 64 bit only, we can use bit masking only for small arrays. If we consider the time factors, then, size of ideal array should not be more than 20. So, if you see any problem with small constraints in any contest, then, there is high probability that it will be solved using Bit Masking.
We have seen how to represent set using a Bit Mask. Now, let’s see some of the basic functions offered by Bit Mask:

  1. bit(i, mask) returns ith bit of mask.
  2. count(mask) returns the number of set bits (elements) in the mask.
  3. set(i, mask) set the ith bit if mask (add the element to the set).
  4. unset(i, mask) unset the ith bit of mask (remove element from the set).

You can create more utility functions as per your requirement. Let’s write code for these functions.

Code

class Bitmask {

    private:
        int mask;
        
    public:

        Bitmask(int x) {
            this->mask = x;
        }
    
        int getMask();
        void setMask(int mask);
        bool bit(int i);
        int count();
        void set(int i);
        void unset(int i);
};

int Bitmask::getMask() {
    return this->mask;
}

void Bitmask::setMask(int mask) {
    this->mask = mask;
}

bool Bitmask::bit(int i) {
    return getMask() & (1 << i);
}

int Bitmask::count() {
    int cnt = 0;
    for (int i=0; i<32; i++) {
        cnt += bit(i);
    }
    return cnt;
}

void Bitmask::set(int i) {
    setMask( getMask() | (1 << i));
}

void Bitmask::unset(int i) {
    setMask( getMask() & (~(1 << i)));
}

So, we have seen the how Bit Masking works. One thing which I have not told you is that it can make implementation in many cases a lot easier. It also let us implement iterative solution of some problems which can only be implemented in recursive manner if Bit Masking is not used. One of such problem is subset sum problem.

Subset sum problem

Given an array A[] of size n < 20 of integers, the task is to print sum of all the subsets of this array.

Solution

It can be easily implemented recursively but if it comes to iterative implementation, then, anybody will shit in their pants if they don’t know Bit Masking. As I have told you that you can represent a set using an integer. We will consider an integer of size n bits where ith bit represent whether element is in subset or not. Clearly, there can be total 2n+1 such integers from 0 to 2n. So, to find sum of each subset, we will simply iterate from 0 to 2n and find and print the sum of each subset.
Let’s write the code for this approach.

Code
#include <bits/stdc++.h>

using namespace std;

bool getBit(int i, int mask) {
    return mask & (1 << i);
}

void printSum(int arr[], int n) {

    for (int i=0; i<(1<<n); i++) {

        int sumSubset = 0;
        for (int j=0; j<n; j++) {
            sumSubset += getBit(j, i) ? arr[j] : 0;
        }
        cout << sumSubset << " ";
    }
}

int main() {

    int arr[] = {1, 2, 3, 4};

    int n = sizeof(arr)/sizeof(arr[0]);

    printSum(arr, n);
}

I think that’s enough of Bit Masking introduction for today. But don’t worry I have just started and in coming tutorials, I will discuss Bit Masking with dynamic programming.
So, that’s it guys for today. I hope you would have enjoyed this tutorial. If you liked this tutorial, then, please follow my blog and share it with your friends. Meanwhile, don’t forget to solve problem on hackerearth.
You can subscribe to my YouTube channel for video tutorials on competitive programming.
You can connect with me on LinkedIn. To get all of your queries answered, you can message me on Quora. Follow me on medium for more of my writings.

Leave a Reply

%d bloggers like this: