Bit Tricks for Competitive Programming

How to invert every bit of a number?/How to take 1’s complement?

To invert every bit in a number like if a number has a bit as 000011010 then after inverting it will become 111100101 we can use the negation operator ‘~’.This is one of the common bit tricks used in most of the cp problems.

Example: x  = 5 the binary form for x is 101 and its inverted form is 010 which is -6.

Code

// bit tricks :  to invert every bit of a number
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int x = 5;
 
    // Inverting all the bits for a number
    cout << (~x);
    return 0;
}

Output:

-6

How to check if the ith bit is set or not in a given number?

Make a mask in such a way that it has ith bit set and the rest are unset. You can do this with the help of the first example. After making the mask do And with the given number.

For example, x  = 5 the binary form for x is 101, and if the position is 0th means we have to check the 0th position if it is set or not for that we can make a mask such that all the bits in the mask is 0 and bit at ith position is set which is 0th position in this case so the mask will be 010 now taking and of the number with the mask will give 101 or 001  =  001 so it has set the bit at 0th position.

Code:

// bit tricks : to check if ith bit is set or not in a given number
#include <bits/stdc++.h>
using namespace std;
int main()
{

   // Number
   int x = 5;

	// Position
     int i = 0;

	// Building mask by making a number such that it has ith bit set
    int mask = 1<<i ;
	bool ans  = x & mask;
	cout <<ans<< endl;
	return 0;
}

Output:

1

How to unset ith bit in a given number?

In this problem, make a mask in such a way that the bit which we want to unset should have 0 and rest all the bits are 1 for this, we can first set the ith bit of our mask and then can use negation operation to invert all the bits. Now we can use this mask and perform the &(And) operation with the number to unset the ith bit.

Example: x  = 7 the binary form for x is 111 and if the position is 1 means we have to unset the 1st position of x for that we can make a mask such that all the bits in the mask is 0 and bit at ith position is set now we will invert all the bits of the mask such that all the bits of the mask are set except for the ith bit. So after inverting the mask, it would look like 11….101 After taking the and of the mask and number that is 111 and 11…101 it would be like 00101 which has unset the ith bit.

Code:

// bit tricks : unset ith bit in a given number
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int x = 7;
    int i = 1;

    // First step is to make a mask that has all 1's except the given position.
    int mask  = (~(1 << i));
    x = x & mask;
    cout << x << endl;
    return 0;
}

Output:

5

You can also read about mock interview.

How to invert a bit at ith position in a given number?

In this problem, make a mask in such a way that it has an ith bit set and then simply xor the mask with the number. Remember, this xor is used to toggle.

Example: x  = 4 the binary form for x is 100 and if the position is 1 means we have to invert the 1st position of the x for that we can make a mask such that all the bits in the mask is 0 and bit at ith position is set which is 1st position in this case so the mask will be 010 now taking xor of the number with the mask will give 100 xor 010  =  110 so it has inverted the bit at 1st position.Always use xor if you want to flip the bits.

Code:

// bit tricks : invert a bit at ith position
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int x = 4;
    int i = 1;
    
    // First step is to make mask by shifting 1 to ith position
    int mask  = 1<<i;
    
    // And the second step is to XOR with given number
    x = x^mask;
    cout<<x;
    return 0;
}

Output:

6

How to find two’s complement of a number?

In this problem, first, we need to find one's complement, and then we can add 1 to get the two's complement. You can refer this to understand the one’s and two's complement we have already discussed the same in detail here.

Code:

// bit tricks : Find two’s complement of a number 
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int x = 4;
    
    // Negative of a number is two's complement
    int twosComplement = -x;
    cout<< (~x+1) << endl;
    return 0;
}

Output:

-4

How to find the lowest set bit of a number?

We can solve this using a small trick.If the given number is x then we can find the lowest set by doing this x&-x.

Suppose x = 101011

Then -x = 010100+1 = 010101

So x&-x = 000001

Code:

// bit tricks : lowest set bit of a number
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int x = 10;
    int lastSetBit = x & -x;
    cout << lastSetBit << endl;
    return 0;
}

Output:

2

Division and Multiplication by 2

Multiplication:

If you want to multiply a number by 2 then you need to left-shift the number by 1 that is 

number << 1 if a number is 4 then 00….0100 after doing left shift by one time it will become 000…1000 which is 8 that is 4*2 = 8

Code:

// bit tricks : Multiplication
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int x = 7;
    int ans = x<<1;
    cout << ans << endl;
    return 0;
}

Output:

14

Division:

Division:

If you want to divide the number by 2 you can do right shift by 1 that is if a number is 000..100, which is 4 doing right shift by one will make it 000…0010, which is 2 (4/2) 

Code:

// bit tricks :  division:
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int x = 7;
    int ans = x>>1;
    cout << ans << endl;
    return 0;
}

Output:

3

How to check if a number is odd or not?

Example: x = 7 which can be represented as 111 in the binary form if we are performing an operation with this number and  1 it will give 0000001 which is true for all the odd numbers.If we consider an example of an even number like x = 4 100 that will always give 0 on performing and with 1.

Code:

// bit tricks : check if a number is odd or not
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int x = 7;
    if(x&1)
    cout<<"Odd";
    else 
    cout<<"Even";
    return 0;
}

Output:

Odd

FAQs

1. Why is bit manipulation considered here rather than normal programming?
   Ans: Working on bits is very handy. It is very fast, so it makes a huge impact while solving competitive programming.
2.  How many bits are present in a number’s binary representation?
   Ans:(log2n) + 1 bits are present in a number’s binary representation.

Key Takeaways

We hope that this blog has helped you enhance your knowledge regarding this topic, and if you would like to learn more, check out our articles on  Coding Ninjas Studio. You can also consider our competitive programming course to give your career an edge over others! 

Do upvote our blog to help other ninjas grow. Happy Coding!”