Given a number n
, toggle all bits after the most significant bit including the most significant bit.
n=11
4
n=15
0
To toggle a specific bit, we take the XOR of the bit with 1.
We can achieve this two ways:
Here, we discuss the first approach by using a bit mask.
The steps of the first approach are as follows:
Let’s understand this with the help of an example.
Consider n=11
. The binary representation of 11 is 1011
, that is, 4 bits are used to represent 11.
The bit mask is 2^{4} - 1, that is, 15.
1011
1111
0100
Hence, the output is 4.
#include<bits/stdc++.h>using namespace std;int toggle(int num) {int n = (int)log2(num) + 1;int mask = pow(2, n) - 1;return num ^ mask;}int main(){int num = 11;cout << toggle(num);}
Line 5: The toggle
function is initialized.
Line 6: We get the noOfBits
by taking the log base 2 of the num
and adding 1
to it.
Line 7: We get the bit mask by taking 2
raised to the power of noOfBits
and then subtracting by 1
Lines 11–15: We initialize the num
and print the resulting output.