Bit-manipulation: a useful topic for Competitive Programming

Hello there ✋, Today I am going to tell you some useful concepts of bitwise operators which you can use in competitive programming to improve the efficiency of your code.

First Let us Understand all Bitwise Operators one by one.

This bitwise & operator takes two bits/numbers as operands and return 1 if both bits are 1 otherwise return 0.

Ex: 1&1 = 1, 1&0 = 0, 0&0 = 0.

This bitwise | operator takes two bits or numbers as operands and return 0 if both bits are 0 otherwise return 1.

Ex: 1|1 = 1, 1|0 = 1, 0|0 = 0.

This bitwise ^ operator takes two bits or numbers as operands and return 0 if both bits are the same otherwise 1.

Ex: 1 ^ 1 = 0, 1 ^ 0 =1.

Two Most Important Property of Bitwise XOR operator is:

I. a^a = 0 (XOR of two same number is 0)

II. 0^a = a (XOR of a any number with 0 is number itself)

This Bitwise Operator takes two numbers as operands and shifts the first number’s bits towards left by the given number (second number ) of time. Its expression is a<<b.

Ex: 1<<1 = 2.

Here a= 1,b=1. Binary of 1 = 01, shifting its bits towards left by 1 (b), we get 10 which is equal to 2. So 1<<1 = 2.

Some Other useful observation is here that left shift (a,b) is equal to a*pow(2,b).

a<<b = a*pow(2,b). In above example, 1<<1 = 1*pow(2,1) = 1*2 = 2.

This Bitwise Operator takes two numbers as operands and shifts the first number’s bits towards Right by the given number (second number ) of time. Its expression is a>>b.

Ex: 4>>1 = 2.

a = 4, b = 1. Binary of a = 100, shifting right by 1 time, we get 010 = 2. So 4>>1 = 2.

Some Other useful observation is here that left shift (a,b) is equal to a/pow(2,b).

a>>b = a/pow(2,b). In above example, 4>>1 = 4/pow(2,1) = 4/2 = 2.

This Bitwise Operator is a Unary Operator means it takes only one number and inverts the bits of that number.

Ex: ~4 = 3.

As we know binary(4) = 100, by using not operator, 1 -> 0 and 0->1. So ~100 = 011 which is 3.

Now let's do some Basic Questions based on these concepts.

Suppose we have to multiply a number by a power of 2, instead of using the multiplication operator and power function, we can use the bitwise left shift operator here. As I have already mentioned above that a<<b = a*pow(2,b).

So Code is just ans = a<<b.

Suppose we have to Divide a number by a power of 2, instead of using the Divide operator and power function, we can use the bitwise Right shift operator here. As I have already mentioned above that a>>b = a/pow(2,b).

So Code is just ans = a>>b.

In this Question, we have to swap elements of two variables. Like a = 7, b = 8 after swapping a = 8, b = 7.

What our General Approach is to store variable “a” into another variable like temp, and put value of “b” in “a” and again put value temp in “b”.

int temp = a;
a = b;
b = a;

But we can use Bitwise XOR here. The code is shown below:

int temp = a^b;
a = temp^a;
b = temp^b;

How the above code is working. As Earlier mentioned Bitwise XOR property numbers 1 & 2 are working here.

In First line temp = a^b. we are storing xor of a and b.
In the second line what we are doing a = temp^a ( a^b^a), So
a^a = 0 (Property number 1), and 0^b which is b, it is assigned to a.
In the third line what we are doing b= temp^b ( a^b^b), So
b^b = 0 (Property number 1), and 0^a which is a, is assigned to b.

Suppose we are given a situation that we have to check that the given number is odd or even.
So What we do?
We quickly use the modulo (%) operator to check it, but what if are said not to use the modulo operator. In that situation, we can use the Bitwise AND(&) operator.
How does it work? we use the below expression.

Every number is odd if it’s left most bit is 1, otherwise even.

if(num&1){
cout<<”Number is Odd”;
}else{
cout<<”Number is Even”;
}

Example:
num = 4 (100).
100 & 001 = 0. (Even Number)
num = 7 (111).
111 & 001 = 1 (Odd Number)

Suppose we are given a number 5 (101). we have to set the second bit of number and have to get the result as 111 = 7.

So Approach here would be to use a combination of left-shift operator and or Operator.

Step: 1
Firstly we will have to left shift 1 by bit which we have to set.
Means if we are given num = 5, bit = 2.
So temp = 1<<(bit-1)
Step: 2
In the Second Step, we will do or of this temp with the given number.
num = num | temp

So Programme would be as follows:

int num = 5;
int bit = 2;
int temp = 1<<(bit-1);
num = num | temp;

The above code’s explanation can be seen in the below image.

As Show in the above picture, we have successfully set the 2-bit number.

Now there are plenty of other questions based on the above concepts. Like I am writing some more basic questions which you can try yourself.

6. To turn off the ith bit of a number.
7. To Check if a number is power of two or not.
8. To Find min/max of two numbers.
9. to count all set bit in a given number.
10. to flip ith bit of number. (means if it 0 then convert it to 1, if it is 1 then to 0).

I am attaching some more links to questions which you can try.

  1. Majority Element
  2. Reverse Bits
  3. Subsets
  4. Missing Number
  5. Power of 4
  6. Find Two Missing Numbers
  7. Sum Of Two Integers
  8. Find the repeating and the missing

If You want to learn more about bit manipulation, you can check out the below resource.

Thank You very much 🙏.

A passionate Computer programmer, making my path towars development field.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store