Toggle bits of a number except first and last bits
Given a number, the task is to toggle bits of the number except the first and the last bit.
Examples:
Input : 10 Output : 12 Binary representation:- 1 0 1 0 After toggling first and last : 1 1 0 0 Input : 9 Output : 15 Binary representation : 1 0 0 1 After toggling first and last : 1 1 1 1
Prerequisite: Find most significant set bit of a number
- Generate a number that contains the middle bit as a set. We need to change all middle bits to 1 and keep corner bits as
- The answer is XOR of generated number and original number. Note that XOR of 1 with a number toggles the number.
C++
// C++ Program to toggle bits // except first and last bit #include<iostream> using namespace std; // return set middle bits int setmiddlebits( int n) { // set all bit n |= n >> 1; n |= n >> 2; n |= n >> 4; n |= n >> 8; n |= n >> 16; // return middle set bits // shift by 1 and xor with 1 return (n >> 1) ^ 1; } int togglemiddlebits( int n) { // if number is 1 then // simply return if (n == 1) return 1; // xor with // middle bits return n ^ setmiddlebits(n); } // Driver Code int main() { // Given number int n = 9; // print toggle bits cout<<togglemiddlebits(n); return 0; } |
Java
// Java program for toggle bits // expect first and last bit import java.io.*; class GFG { // return set middle bits static int setmiddlebits( int n) { // set all bit n |= n >> 1 ; n |= n >> 2 ; n |= n >> 4 ; n |= n >> 8 ; n |= n >> 16 ; // return middle set bits // shift by 1 and xor with 1 return (n >> 1 ) ^ 1 ; } static int togglemiddlebits( int n) { // if number is 1 then // simply return if (n == 1 ) return 1 ; // XOR with middle bits return n ^ setmiddlebits(n); } // Driver Code public static void main (String[] args) { // Given number int n = 9 ; // print toggle bits System.out.println(togglemiddlebits(n)); } } // This code is contributed by vt_m |
Python3
# Python3 program for toggle bits # expect first and last bit # return set middle bits def setmiddlebits(n): # set all bit n | = n >> 1 ; n | = n >> 2 ; n | = n >> 4 ; n | = n >> 8 ; n | = n >> 16 ; # return middle set bits # shift by 1 and xor with 1 return (n >> 1 ) ^ 1 def togglemiddlebits(n): # if number is 1 then simply return if (n = = 1 ): return 1 # xor with middle bits return n ^ setmiddlebits(n) # Driver code n = 9 print (togglemiddlebits(n)) # This code is contributed by Anant Agarwal. |
C#
// C# program for toggle bits // expect first and last bit using System; class GFG { // return set middle bits static int setmiddlebits( int n) { // set all bit n |= n >> 1; n |= n >> 2; n |= n >> 4; n |= n >> 8; n |= n >> 16; // return middle set bits // shift by 1 and xor with 1 return (n >> 1) ^ 1; } static int togglemiddlebits( int n) { // if number is 1 then // simply return if (n == 1) return 1; // XOR with middle bits return n ^ setmiddlebits(n); } // Driver Code public static void Main () { // Given number int n = 9; // print toggle bits Console.WriteLine(togglemiddlebits(n)); } } // This code is contributed by Anant Agarwal. |
PHP
<?php // Php Program to toggle bits // except first and last bit // return set middle bits function setmiddlebits( $n ) { // set all bit $n |= $n >> 1; $n |= $n >> 2; $n |= $n >> 4; $n |= $n >> 8; $n |= $n >> 16; // return middle set bits // shift by 1 and xor with 1 return ( $n >> 1) ^ 1; } function togglemiddlebits( $n ) { // if number is 1 then // simply return if ( $n == 1) return 1; // xor with // middle bits return $n ^ setmiddlebits( $n ); } // Driver Code $n = 9; // print toggle bits echo togglemiddlebits( $n ); // This code is contributed by ajit ?> |
Javascript
<script> // Javascript Program to toggle bits // except first and last bit // return set middle bits function setmiddlebits(n) { // set all bit n |= n >> 1; n |= n >> 2; n |= n >> 4; n |= n >> 8; n |= n >> 16; // return middle set bits // shift by 1 and xor with 1 return (n >> 1) ^ 1; } function togglemiddlebits(n) { // if number is 1 then // simply return if (n == 1) return 1; // xor with // middle bits return n ^ setmiddlebits(n); } // Driver Code // Given number var n = 9; // print toggle bits document.write(togglemiddlebits(n)); </script> |
15
Time Complexity: O(log2n), where n is the given number
Auxiliary Space: O(1)
Another Approach: Using bit mask
The idea to solve this problem is that we can use XOR of a specific bit with 1 to toggle the specific bit. Therefore, for an n – bit number, we can construct a bit mask of the form 0111….11110, ie, an n – bit number, where all bits are set except the first and last bit. Therefore, for a number that is greater than or equal to 4, the bit mask is equal to 2n – 2. (n can be calculated using log2number) (For numbers less than 4, there are no middle bits, therefore, the number will not be changed).
Approach:
- Calculate the bit mask = 2 log2number – 2
- Perform the XOR of the number and the mask.
Below is the implementation of the above approach:
C++
// C++ Program to toggle bits // except first and last bit #include<bits/stdc++.h> using namespace std; //function to toggle the middle bits //using the bit mask int togglemiddlebits( int n) { //if n < 4, there are no middle bits if (n < 4) return n; int mask = (1 << ( int )log2(n)) - 2; return mask ^ n; } // Driver Code int main() { // Given number int n = 9; //Function call cout << togglemiddlebits(n) << endl; return 0; } //This code is contributed by phasing17 |
Java
// Java Program to toggle bits // except first and last bit import java.io.*; import java.util.*; class GFG { // function to toggle the middle bits // using the bit mask public static int togglemiddlebits( int n) { // if n < 4, there are no middle bits if (n < 4 ) return n; int mask = ( 1 << ( int )(Math.log(n) / Math.log( 2 ))) - 2 ; return mask ^ n; } // Driver Code public static void main(String[] args) { // Given number int n = 9 ; //Function call System.out.println(togglemiddlebits(n)); } } // this code is contributed by adityapatil12 |
Python3
# python3 Program to toggle bits # except first and last bit import math #function to toggle the middle bits #using the bit mask def togglemiddlebits(n) : #if n < 4, there are no middle bits if n < 4 : return n mask = int (( 1 << int (math.log2( 14 ))) - 2 ) return mask ^ n # Driver code if __name__ = = "__main__" : # Given number n = 9 # Function call print (togglemiddlebits(n)) # this code is contributed by aditya942003patil |
C#
// C# Program to toggle bits // except first and last bit using System; class GFG { // function to toggle the middle bits // using the bit mask static int togglemiddlebits( int n) { // if n < 4, there are no middle bits if (n < 4) return n; int mask = (1 << ( int )(Math.Log(n) / Math.Log(2))) - 2; return mask ^ n; } // Driver Code public static void Main( string [] args) { // Given number int n = 9; // Function call Console.WriteLine(togglemiddlebits(n)); } } // This code is contributed by phasing17 |
Javascript
// JavaScript Program to toggle bits // except first and last bit //Function to toggle the middle bits //using the bit mask function togglemiddlebits(n) { //if n < 4, there are no middle bits if (n < 4) return n; let mask = (1 << Math.floor(Math.log2(n))) - 2; return mask ^ n; } // Driver Code // Given number let n = 9; //Function call console.log(togglemiddlebits(n)); //This code is contributed by phasing17 |
15
Time Complexity: O(1)
Auxiliary Space: O(1)
Contact Us