Bitmasking and C++ bitset

What is Bitmasking?

At the Smallest scale in computers, data is stored as bits. A bit stores either 0 or 1. A binary number is a number expressed in the base-2 system. Each digit can be either 0 or 1.

You can check the binary representation of a number in python:

>>> bin(21)
'0b10101'

So, 21 is represented as ‘10101’ in Binary.

Bitmask

Now finally, what’s a mask? We can construct a binary number such that a particular digit is set to 1 and other digits are set to 0. This creates a “mask” that when we AND it to another binary it "turns off" (set to 0) all digits except the 1 digit in the mask.

Common Bitmask Operations

1. (number | (1 << i))
   this operation sets the ith bit in the number to 1.
2. (number & ~(1 << i))
   this operation sets the ith bit in the number to 0.
3. (number & (1 << i))
   this operation checks if the ith bit in the number is set to 1 or not.
   and so on.

more bitmask operations -

Bitset in C++

In C++, A Bitset is a data structure that is used to represent a set of bits. It is similar to an array, but instead of storing integers or characters, it stores binary values. Bitsets are commonly used in computer graphics, network programming, and cryptography.

In C++, a Bitset is implemented using the std::bitset class. This class provides a set of operations for manipulating and querying the bits in the bitset. For example:

#include <bitset>
#include <iostream>

using namespace std;

int main() {
    bitset<8> bits("10100101");

    cout << bits << endl; // prints "10100101"
    cout << bits.count() << endl; // prints "4"
    cout << bits.any() << endl; // prints "true"
    cout << bits.none() << endl; // prints "false"
    cout << bits.test(3) << endl; // prints "true"
    cout << bits.set(2) << endl; // prints "10101101"
    cout << bits.reset(1) << endl; // prints "10101100"
    cout << bits.flip() << endl; // prints "01010011"

    return 0;
}

Here’s an example of how to use bitset for masking:

// C++ program to demonstrate various functionality of bitset
#include <bits/stdc++.h>
using namespace std;

#define M 32

int main()
{
 // default constructor initializes with all bits 0
 bitset<M> bset1;

 // bset2 is initialized with bits of 20
 bitset<M> bset2(20);

 // bset3 is initialized with bits of specified binary string
 bitset<M> bset3(string("1100"));

 // cout prints exact bits representation of bitset
 cout << bset1 << endl; // 00000000000000000000000000000000
 cout << bset2 << endl; // 00000000000000000000000000010100
 cout << bset3 << endl; // 00000000000000000000000000001100
 cout << endl;

 // declaring set8 with capacity of 8 bits

 bitset<8> set8; // 00000000

 // setting first bit (or 6th index)
 set8[1] = 1; // 00000010
 set8[4] = set8[1]; // 00010010
 cout << set8 << endl;

 // count function returns number of set bits in bitset
 int numberof1 = set8.count();

 // size function returns total number of bits in bitset
 // so there difference will give us number of unset(0)
 // bits in bitset
 int numberof0 = set8.size() - numberof1;

 cout << set8 << " has " << numberof1 << " ones and "
  << numberof0 << " zeros\n";

 // test function return 1 if bit is set else returns 0
 cout << "bool representation of " << set8 << " : ";
 for (int i = 0; i < set8.size(); i++)
  cout << set8.test(i) << " ";

 cout << endl;

 // any function returns true, if atleast 1 bit
 // is set
 if (!set8.any())
  cout << "set8 has no bit set.\n";

 if (!bset1.any())
  cout << "bset1 has no bit set.\n";

 // none function returns true, if none of the bit
 // is set
 if (!bset1.none())
  cout << "bset1 has some bit set\n";

 // bset.set() sets all bits
 cout << set8.set() << endl;

 // bset.set(pos, b) makes bset[pos] = b
 cout << set8.set(4, 0) << endl;

 // bset.set(pos) makes bset[pos] = 1 i.e. default
 // is 1
 cout << set8.set(4) << endl;

 // reset function makes all bits 0
 cout << set8.reset(2) << endl;
 cout << set8.reset() << endl;

 // flip function flips all bits i.e. 1 <-> 0
 // and 0 <-> 1
 cout << set8.flip(2) << endl;
 cout << set8.flip() << endl;

 // Converting decimal number to binary by using bitset
 int num = 100;
 cout << "\nDecimal number: " << num
  << " Binary equivalent: " << bitset<8>(num);

 return 0;
}

/* OUTPUT

00000000000000000000000000000000
00000000000000000000000000010100
00000000000000000000000000001100

00010010
00010010 has 2 ones and 6 zeros
bool representation of 00010010 : 0 1 0 0 1 0 0 0 
bset1 has no bit set.
11111111
11101111
11111111
11111011
00000000
00000100
11111011

Decimal number: 100 Binary equivalent: 01100100

*/

Conclusion

One of the biggest benefits of using Bitmask and Bitset in C++ is their efficiency. Bitwise operations are much faster than arithmetic operations and can be used to manipulate multiple bits at once. This makes them ideal for working with large datasets in Competitive Programming competitions.