How to toggle all bits after MSB

Problem statement

Given a number n, toggle all bits after the most significant bit including the most significant bit.

Example 1

  • Input: n=11
  • Output: 4

Example 2

  • Input: n=15
  • Output: 0

Solution

To toggle a specific bit, we take the XOR of the bit with 1.

We can achieve this two ways:

  1. By using a bit mask.
  2. By looping via bit by bit until the MSB is reached.

Here, we discuss the first approach by using a bit mask.

The steps of the first approach are as follows:

  1. Find the number of bits of the number. The bit mask is 2n - 1. We can find the number of bits of the number by taking the log of the number and adding one to it.
  2. Do a bitwise XOR with the bit mask and the number.

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 24 - 1, that is, 15.

  • 11: 1011
  • 15: 1111
  • 11 XOR 15: 0100

Hence, the output is 4.

Code

#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);
}

Explanation

  • 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.

Free Resources

License: Creative Commons-Attribution-ShareAlike 4.0 (CC-BY-SA 4.0)