 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 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:

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.

``````// 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.

``````// 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)

// Build a Mask 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