# Understanding Bit mask/ Bit map in depth

#### Data Structures Algorithms bit mask bitwise operation Get FREE domain for 1st year and build your brand new site

Bit manipulation is the act of algorithmically manipulating bits or other pieces of data shorter than a byte.

Now , What is Bit Mask?

A bit mask (or Bitmap) is a data structure, usually an integer or array of bits, that represent a bit pattern which signifies a particular state in a particular computational problem. It takes advantage of bitwise operations.

## Example

Consider a situation where you have 5 computers which you assign to your guests. When a new guest arrives or some other event, you need to have information of the computers available or already assigned.

In short, we need the current state of the 5 computers.

There are many ways in which this problem can be represented like:

• list of computer objects

In the bit mask approach, we will have a 5 bit number where the ith bit conveys information:

• if ith bit is set to 1, ith computer is occupied
• if ith bit is set to 0, ith computer is free

Hence, 01101 represents:

• Computer 2, 3 and 5 are occupied
• Computer 1 and 4 are free

## Why we use bit mask?

• it is memory efficient in most problems

• it is computational efficient as we can use bitwise operations which are natively supported by the computer system and will be faster than other operations like addition (+).

## Common bit operations

• Turning on bit:
[ 0 -> 1 | 1 -> 1 ]

• Turning off bit:
[ 1 -> 0 | 0 -> 0 ]

• Toggle specific bit:
[ 1 -> 0 | 0 -> 0 ]

• Querying Bit:
[ Check whether particular bit is 0 or 1 ]

### bit Operators :

• (&) - Bitwise AND
• (|) - Bitwise OR
• (^) - Bitwise XOR (Exclusive OR)
• (!) - Bitwise complement
• (<<) - Left Shift
• (>>) - Right Shift ### Example :

First Let's take one random number:

178 // base 10 (decimal)
10110010 // base 2 (binary)

data = 178

I will use this number through out the article

### 1) Quering Bit :

Quering Bit means check particular bit whether it is 0 or 1 at desired position. For that first i have to build a mask.

• Let's check 3rd bit is 0 or 1
``````// Build a Mask
``````

How? We can have given mask by left shift of 1 by 2 times that is,

``````mask = 1 << 2
``````

Now , AND(&) of data with mask

``````data    10110010
________
ans =   00000000
``````

if(ans is ZERO)
desired bit is zero (0)

if(ans is NON ZERO)
desired bit is one (1)

ans = 0 (base 10)
here, ans is ZERO so, 3rd bit is 0 :)

Why? Here we have used AND(&) operator...
x & 0 = 0
x & 1 = x (x = 0/1)

• Let's check 5th bit is 0 or 1

Same procedure ,

``````// Build a mask
``````

// AND(&) of data with mask

``````data    10110010
________
ans =   00010000
``````

ans = 16 (base 10)
here, ans is NON ZERO so, 5th bit is 1 :)

Hack is we are anding(&) by 1 only with our desired bit so if it is 1 then answer will obvious non zero and if it is zero then all bits in answer will be zero.
So , answer (data & mask) is NON_ZERO iff desired bit is set or 1. If answer is zero then desired bit is 0.

### 2) Turning Bit On :

If we want to set perticular bit to 1 then Bit Mask will help us.

• Let's set 7th bit to 1
``````// Build a Mask
mask = 01000000  (7th bit 1 others 0)

// OR(|) of data with mask
data    10110010
________
ans =   11110010
``````

Why? Here we have used OR(|) operation

Hack is OR(|) will give ans 0 iff both bits are 0 otherwise it will gives 1

x | 0 = x
x | 1 = 1 (x = 0/1)

Hack is if we do OR(|) of 1 with anything (0/1) it will set ans to 1. So, here we are doing OR(|) operation with our desired bit and it will set that bit to 1. And if We do OR(|) by 0 with any other bit it it will not change that bit.

### 3) Turning Bit Off :

If we want to set perticular bit to 0 then Bit Mask will help us.

• Let's set 2nd bit to 0
``````// Build a Mask
mask = 11111101  (2nd bit 0 others 1)

How?
mask = ~(1<<2)  [Bitwise complement(~) operator : it will flip all bits ~(11110000) = (00001111)]

// AND(&) of data with mask
data    10110010
________
ans =   10110000
``````

Got it?? Because we have used AND(&) :)

Hack is if we do AND(&) of 0 with anything (0/1) it will set ans to 0. So, here we are doing AND(&) operation with our desired bit and it will set that bit to 0. And if We do AND(&) by 0 with any other bit it it will not change that bit.

### 4) Toggling Bit :

If we want to toggle bits that is 0->1 or 1->0 then Bit Mask will help us.

• Let's toggle 4 bits [1,2,6,7] of data (10110010)

mask = 01100011 (1st , 2nd , 6th , 7th bits are 1 others are 0)

How?

``````mask = (1<<6) | (1<<5) | (1<<1) | (1<<0)

// XOR(^) of data with mask
data    10110010
________
ans =   11010001
``````

Why? Because we have used XOR(^) operator

Hack is if we do XOR(^) of 0 with anything (0/1) it will not change that bit. So, here we are doing XOR(^) operation with our desired bit and it will put it as it is. And if We do XOR(^) by 1 with any other bit it it will flip that bit.

x ^ 0 = x [0^0 = 0 , 1^0 = 1]
x ^ 1 = ~x [0^1 = 1 , 1^1 = 0] x = {0/1}

## Code example

I suggest you go through code it is very simple. I have made function for all above operations. You have to pass data and position of bit on which you want to perform operation.

``````    #include <bits/stdc++.h>
using namespace std;

void queryBit(int data , int position){

cout << "Check for " << position << " Bit" << endl;

// storing data
data = 178;
cout << "data  :  " << bitset<8>(data) << endl;

// Bitwise AND(&) between data and mask
cout << "ans   :  " << bitset<8>(ans) << endl;

if(ans == 0)  // If ZERO then desired bit is 0
cout << "Bit at position " << position << " is = " << 0 << endl;
else  // If NON_ZERO then desired bit is 1
cout << "Bit at position " << position << " is = " << 1 << endl;

cout << endl;
}

void setTo1(int data , int position){

cout << "Set to 1 at position " << position << endl;

// storing data
data = 178;
cout << "data  :  " << bitset<8>(data) << endl;

// Bitwise OR(|) between data and mask
cout << "ans   :  " << bitset<8>(ans) << endl;

cout << endl;
}

void setTo0(int data , int position){

cout << "Set to 0 at position " << position << endl;

// storing data
data = 178;
cout << "data  :  " << bitset<8>(data) << endl;

// Bitwise AND(&) between data and mask
cout << "ans   :  " << bitset<8>(ans) << endl;

cout << endl;
}

void toggleBits(int data , int position){

cout << "Toggle bit at position " << position << endl;

// storing data
data = 178;
cout << "data  :  " << bitset<8>(data) << endl;

// Bitwise XOR(^) between data and mask
cout << "ans   :  " << bitset<8>(ans) << endl;

cout << endl;
}

int main(){

int data = 178;          // our data - 10110010

queryBit(data,2);
queryBit(data,3);

setTo0(data,2);
setTo0(data,3);

setTo1(data,2);
setTo1(data,3);

toggleBits(data,2);
toggleBits(data,3);

return 0;
}
``````

Output:

``````Check for 2 Bit
data  :  10110010
ans   :  00000010
Bit at position 2 is = 1

Check for 3 Bit
data  :  10110010
ans   :  00000000
Bit at position 3 is = 0

Set to 0 at position 2
data  :  10110010
ans   :  10110000

Set to 0 at position 3
data  :  10110010
ans   :  10110010

Set to 1 at position 2
data  :  10110010
ans   :  10110010

Set to 1 at position 3
data  :  10110010
ans   :  10110110

Toggle bit at position 2
data  :  10110010
ans   :  10110000

Toggle bit at position 3
data  :  10110010
ans   :  10110110
``````

## Practical use

• In programming languages such as C, bit fields are a useful way to pass a set of named boolean arguments to a function.

• Masks are used with IP addresses in IP ACLs (Access Control Lists) to specify what should be permitted and denied.

• In computer graphics, when a given image is intended to be placed over a background, the transparent areas can be specified through a binary mask. #### Ajay Bechara

Intern at OpenGenus | Bachelor of Technology (2017 to 2021) in Information and Communication Technology at Ahmedabad University