### Bitmasking

**BITMASKING CONCEPTS**

Any number can be represented in the form of 0’s and 1’s.

Number is represented in the power of 2.

Q:- Why we need bitmasking ? Ans:- Arthimetic operations on decimal number takes a lot of time internally for calculation. If we calculate it in terms of 0's and 1's, it will perform faster.

There are two types of compliment :-

1:- 1’s compliment

2:- 2’s compliment

Like we have unit and tenth place in number system , similarly we have LSB and MSB in the Binary Number System.

**The Least Significant Bit(LSB) is the bit position in the binary integer giving the unit value which determines whether the given number is even or odd.**

**The Most Significant Bit is the bit position in the binary number to the extreme left of the LSB.**

For example:-

99 in the binary is expressed as (MSB)01100011(LSB) .In this , MSB is 0 and LSB is 1.

Q- How to find 2’s Compliment ?

Scan from the Right Side i.e from LSB and find the first 1 in the given number and write as it is.

Now , compliment every bit i.e make 0 to 1 and 1 to 0.

OR

2’s Compliment of any number Is equal to compliment of that number plus 1;.

Ex – 0 1 0 1 0 0 1 0

2’s Compliment- 1 0 1 0 1 1 1 0

The bitwise Compliment of 35 is 220 in decimal number system.

For finding 2’s compliment , we add 1 to 220 and then find its binary , which is equivalent to -36. Hence the output is -36.

#include <iostream.h> int main() { cout<<~35; cout<<~-12; return 0; }

### Note:- Bitwise complement of any number N is -(N+1).

Bitmasking Operations :-

1:- **OR** (|) -: It is used between the two bits for addition.

It gives 0 if both the bits are 0 and if either if them is 1 , it gives 1.

2:- **AND** (&) :- It is used between the two bits for multiplication.

It gives 1 if both the bits are 1 and if either if them is 1 , it gives 0.

3:- **XOR**(^):- This is the most used operator in the Interview Questions. It gives output 1 if both bits are opposite.

1 ^ 1=0 , 1 ^ 0=1 , 0 ^ 1=1

4:- **Left Shift** (<<):- Basically , it means multiply the binary number by 2.

Initially , the number 7 , in its binary representation is left shift by 1. After shifting the value of x becomes 14 in decimal representation.

Now , then left shift the value of x (which is now 14 ) by 3 ..

So , 14 *2 =28 , 28 * 2= 56 , 56*2=112.

5:- **Right Shift** (>>):- Basically , it means dividing the binary number by 2.

Initially , the decimal equivalent to binary number is 23 ..And after right shifting , the decimal equivalent becomes 11 , which is nearly half of the 23.

**Now let us get through with the basic programs of bitmasking **

**1:- Program to check whether the given number is even or odd using bitmask.**

Algo:-

Step:- Check the last binary bit of the decimal number and AND(&) it with 1.

If it gives 1 , that means the number is odd ,otherwise the number is even.

Code:-

#inlcude<iostream.h> using namespace std; int is even(int n) { if(n & 1 ==1) return 1; else return 0; } int main() { int n=201; int x; x=iseven(n); if(x=0)?cout<<"Number is even" : cout<<"Number is odd"; return 0; }

**Now we introduced here a new term “MASK”.**

A mask is a data that is used to either set or reset or compliment a group of bits in a single bitwise operation. Set:- To Turn ON the bits , we generally use Bitwise “OR” operation. To make sure a bit is ON , we “OR” it with 1. To make a Bit OFF , we “OR” it with 0.

**2:- Program set the ‘i’ bit of a number.**

#include<iostream.h> using namespace std; int setibit(int x, int k) { int mask=1; //initialise mask to 1 mask=1<<(i-1); //mask the binary number to k digit n=n|mask; // OR the number with mask } int main() { int n=25; cout<<setibit(n,4); return 0; }

**3:- Program to add 1 to the number(without using arthimetic operator).**

Step:-

1: Start from the LSB and XOR it with mask till we get 0.

2: Increase the mask , everytime the condition becomes true (while((n&mask!=0))).

3:- Now after coming out of loop , XOR it with the current binary number.

Code:-

#include<iostream.h> using namaspace std; int add_one(int x) { int mask=1; while((n&mask!=0)) //Conditin for mask termination { n=n^mask; // XOR mask with the binary number mask=mask<<1; // increase the value of mask i.e left shift the mask } } int main() { int n=45; cout<<add_one(int k); return 0; }

CommentsNo comment yet.