1 in binary format 0001
0001 --> last bit is set hence odd n.
14 in binary format 1110
&
1 in binary format 0001
0000 --> last bit is not set hence even n.
Code Implementation:
#include<iostream>
using namespace std;
// Returns true if
// n is even
bool isEven(int n)
{
return (!(n & 1));
}
int main()
{
int n = 101;
isEven(n) ? cout << “Even” : cout << “Odd”;
return 0;
}
You can also try this code with Online C++ Compiler
How to set a bit in num: We can set a bit at the nth position in num by using the OR operator. First, we will left shift the bit from 1 to n via (1<<n). Then we use OR to set the bit in num.
Example:
#include<iostream>
using namespace std;
void set(int & num, int pos) {
// (1<<pos) shifting 1 to the pos
num |= (1 << pos);
}
int main() {
int num = 4, pos = 1;
set(num, pos);
cout << (int)(num) << endl;
return 0;
}
You can also try this code with Online C++ Compiler
Output:
6
• How to clear a bit at the nth position in num
We can unset a bit at the nth position ‘num’ with the help of ‘AND’ (&) operator.
• Left shift ‘1’ to n position via (1<<n)
• Use Bitwise NOT operator ‘~’ to unset this shifted ‘1’.
• Now after clearing this left-shifted ‘1’ i.e making it to ‘0’ we will ‘AND'(&) with the number ‘num’ that will unset bit at the nth position.
Example:
#include<iostream>
using namespace std;
// First step is to get a number that has all 1’s except the given position.
void unset(int & num, int pos)
{
//Second step is to bitwise and this number with given number
num &= (~(1 << pos));
}
int main()
{
int num = 7;
int pos = 1;
unset(num, pos);
cout << num << endl;
return 0;
}
You can also try this code with Online C++ Compiler
Toggling a bit at nth position: We can toggle a bit (i.e, set to unset and vice versa). We use the XOR operator to do this purpose because it returns 1 if two bits are odd otherwise 0. The first step will be to shift 1 and then xor with the number.
Example:
#include<iostream>
using namespace std;
void toggle(int & num, int pos) {
num ^= (1 << pos);
}
int main() {
int num = 4;
int pos = 1;
toggle(num, pos);
cout << num << endl; // outputs 6
return 0;
}
You can also try this code with Online C++ Compiler
Checking if the nth bit is set or unset: It is quite easily doable using ‘AND’ operator. Left shift ‘1’ to given position and then ‘AND'(‘&’).
Example:
#include<iostream>
using namespace std;
bool at_position(int num, int pos)
{
bool bit = num & (1 << pos);
return bit;
}
int main()
{
int num = 5;
int pos = 0;
bool bit = at_position(num, pos);
cout << bit << endl;
return 0;
}
You can also try this code with Online C++ Compiler
Output:
1
Observe that we have first left-shifted ‘1’ and then used ‘AND’ operator to get bit at that position. So if there is ‘1’ at position ‘pos’ in ‘num’, then after ‘AND’ our variable ‘bit’ will store ‘1’ else if there is ‘0’ at position ‘pos’ in the number ‘num’ than after ‘AND’ our variable bit will store ‘0’.
Clear all bits from LSB to the ith bit
mask = ~((1 << i+1 ) – 1);
x &= mask;
Logic: To clear all bits from LSB to i-th bit, we have to AND x with mask having LSB to i-th bit 0. To obtain such mask, first left shift 1 i times. Now if we minus 1 from that, all the bits from 0 to i-1 become 1 and remaining bits become 0. Now we can simply take complement of mask to get all first i bits to 0 and remaining to 1.
Example:
x = 29 (00011101) and we want to clear LSB to 3rd bit, total 4 bits
mask -> 1 << 4 -> 16(00010000)
mask -> 16 – 1 -> 15(00001111)
mask -> ~mask -> 11110000
x & mask -> 16 (00010000)
Clearing all bits from MSB to i-th bit
mask = (1 << i) – 1;
x &= mask;
Logic: To clear all bits from MSB to i-th bit, we have to AND x with mask having MSB to i-th bit 0. To obtain such mask, first left shift 1 i times. Now if we minus 1 from that, all the bits from 0 to i-1 become 1 and remaining bits become 0.
Example:
x = 215 (11010111) and we want to clear MSB to 4th bit, total 4 bits
mask -> 1 << 4 -> 16(00010000)
mask -> 16 – 1 -> 15(00001111)
x & mask -> 7(00000111)
- Upper case English alphabet to lower case
ch |= ‘ ‘;
Logic: The bit representation of upper case and lower case English alphabets are:
A -> 01000001 a -> 01100001
B -> 01000010 b -> 01100010
C -> 01000011 c -> 01100011
. .
. .
Z -> 01011010 z -> 01111010
We can set 5th bit of upper case characters, it will be converted into lower case character. Make mask having 5th bit 1 and other 0 (00100000). This mask is a bit representation of the space character (‘ ‘).
Example:
ch = ‘A’ (01000001)
mask = ‘ ‘ (00100000)
ch | mask = ‘a’ (01100001)
- Lower case English alphabet to upper case
ch &= ‘_’ ;
Logic: The bit representation of upper case and lower case English alphabets are:
A -> 01000001 a -> 01100001
B -> 01000010 b -> 01100010
C -> 01000011 c -> 01100011
. .
. .
Z -> 01011010 z -> 01111010
Clear the 5th bit of lower case characters, it will be converted into upper case character. Make a mask having 5th bit 0 and other 1 (10111111). This mask is a bit representation of the underscore character (‘_’). AND the mask with the character.
Example:
ch = ‘a’ (01100001)
mask = ‘_ ‘ (11011111)
ch & mask = ‘A’ (01000001)
Read about Bitwise Operators in C, and Euclid GCD Algorithm here.
Frequently Asked Questions
Which competitive programming sites are good for beginners?
A few websites which are good to practice competitive programming include hackerrank, codechef and once you are comfortable with reading and understanding competitive programming problems, move on to codeforces.
Is it necessary to do competitive programming?
Necessary is relative. If you want to have fun solving puzzles with the help of math and coding, competitive programming is the best.
Can competitive programming get you a job?
Competitive programming helps you prove your mettle as a coder and displays your ability to work under pressure and against time therefore sometimes companies do contact the top performers and at times hiring contests also occur on competitive programming platforms.
Conclusion
This article discussed Bit Manipulation for Competitive Programming. So now, without wasting your time, you start implementing these ways in your regular practice to optimize your code!
You can also consider our competitive programming course to give your career an edge over others.
Attempt our Online Mock Test Series on Coding Ninjas Studio now!
Happy Coding!
85+ registered 