Given a number n, the task is to toggle only first and last bits of a number
Examples :
Input : 10 Output : 3 Binary representation of 10 is 1010. After toggling first and last bits, we get 0011. Input : 15 Output : 6
Prerequisite : Find MSB of given number.
1) Generate a number which contains first and last bit as set. We need to change all middle bits to 0 and keep corner bits as 1.
2) Answer is XOR of generated number and original number.
C++
// CPP program to toggle first and last// bits of a number#include <iostream>using namespace std;// Returns a number which has same bit// count as n and has only first and last// bits as set.int takeLandFsetbits(int n){ // set all the bit of the number n |= n >> 1; n |= n >> 2; n |= n >> 4; n |= n >> 8; n |= n >> 16; // Adding one to n now unsets // all bits and moves MSB to // one place. Now we shift // the number by 1 and add 1. return ((n + 1) >> 1) + 1;}int toggleFandLbits(int n){ // if number is 1 if (n == 1) return 0; // take XOR with first and // last set bit number return n ^ takeLandFsetbits(n);}// Driver codeint main(){ int n = 10; cout << toggleFandLbits(n); return 0;} |
Java
// Java program to toggle first and last// bits of a numberimport java.io.*;class GFG { // Returns a number which has same bit // count as n and has only first and last // bits as set. static int takeLandFsetbits(int n) { // set all the bit of the number n |= n >> 1; n |= n >> 2; n |= n >> 4; n |= n >> 8; n |= n >> 16; // Adding one to n now unsets // all bits and moves MSB to // one place. Now we shift // the number by 1 and add 1. return ((n + 1) >> 1) + 1; } static int toggleFandLbits(int n) { // if number is 1 if (n == 1) return 0; // take XOR with first and // last set bit number return n ^ takeLandFsetbits(n); } // Driver code public static void main(String args[]) { int n = 10; System.out.println(toggleFandLbits(n)); }}/*This code is contributed by Nikita Tiwari.*/ |
Python3
# Python 3 program to toggle first# and last bits of a number.# Returns a number which has same bit# count as n and has only first and last# bits as set.def takeLandFsetbits(n) : # set all the bit of the number n = n | n >> 1 n = n | n >> 2 n = n | n >> 4 n = n | n >> 8 n = n | n >> 16 # Adding one to n now unsets # all bits and moves MSB to # one place. Now we shift # the number by 1 and add 1. return ((n + 1) >> 1) + 1 def toggleFandLbits(n) : # if number is 1 if (n == 1) : return 0 # take XOR with first and # last set bit number return n ^ takeLandFsetbits(n)# Driver coden = 10print(toggleFandLbits(n))# This code is contributed by Nikita Tiwari. |
C#
// C# program to toggle first and last // bits of a numberusing System;class GFG { // Returns a number which has same bit // count as n and has only first and last // bits as set. static int takeLandFsetbits(int n) { // set all the bit of the number n |= n >> 1; n |= n >> 2; n |= n >> 4; n |= n >> 8; n |= n >> 16; // Adding one to n now unsets // all bits and moves MSB to // one place. Now we shift // the number by 1 and add 1. return ((n + 1) >> 1) + 1; } static int toggleFandLbits(int n) { // if number is 1 if (n == 1) return 0; // take XOR with first and // last set bit number return n ^ takeLandFsetbits(n); } // Driver code public static void Main() { int n = 10; Console.WriteLine(toggleFandLbits(n)); }} // This code is contributed by Anant Agarwal. |
PHP
<?php// PHP program to toggle first and last // bits of a number// Returns a number which has same bit// count as n and has only first and last // bits as set.function takeLandFsetbits($n){ // set all the bit of the number $n |= $n >> 1; $n |= $n >> 2; $n |= $n >> 4; $n |= $n >> 8; $n |= $n >> 16; // Adding one to n now unsets // all bits and moves MSB to // one place. Now we shift // the number by 1 and add 1. return (($n + 1) >> 1) + 1;}function toggleFandLbits(int $n){ // if number is 1 if ($n == 1) return 0; // take XOR with first and // last set bit number return $n ^ takeLandFsetbits($n);}// Driver code$n = 10;echo toggleFandLbits($n);// This code is contributed by mits ?> |
Javascript
<script>// JavaScript program to toggle first and last // bits of a number // Returns a number which has same bit // count as n and has only first and last // bits as set. function takeLandFsetbits(n) { // set all the bit of the number n |= n >> 1; n |= n >> 2; n |= n >> 4; n |= n >> 8; n |= n >> 16; // Adding one to n now unsets // all bits and moves MSB to // one place. Now we shift // the number by 1 and add 1. return ((n + 1) >> 1) + 1; } function toggleFandLbits(n) { // if number is 1 if (n == 1) return 0; // take XOR with first and // last set bit number return n ^ takeLandFsetbits(n); }// Driver code let n = 10; document.write(toggleFandLbits(n));</script> |
Output
3
Time Complexity: O(1).
Auxiliary Space: O(1).
Another Approach:
We can do this in two steps by:
To generate an bit mask for n, where only the last and first bits are set, we need to calculate 2log2n + 20
Then, just take the XOR of the mask and n.
Below is the implementation of the above approach:
C++
// CPP program to toggle first and last// bits of a number#include <bits/stdc++.h>using namespace std;//function to toggle first and last bits//of a numberint toggleFandLbits(int n){ //calculating mask int mask = pow(2, (int)log2(n)) + 1; //taking xor of mask and n return mask ^ n;}// Driver codeint main(){ int n = 10; //function call cout << toggleFandLbits(n); return 0;}//this code is contributed by phasing17 |
Java
// Java program to toggle first and last// bits of a numberclass GFG{ // function to toggle first and last bits // of a number static int toggleFandLbits(int n) { // calculating mask int mask = (int)Math.pow( 2, (int)(Math.log(n) / Math.log(2))) + 1; // taking xor of mask and n return mask ^ n; } // Driver code public static void main(String[] args) { int n = 10; // Function call System.out.println(toggleFandLbits(n)); }}// this code is contributed by phasing17 |
Python3
# Python3 program to toggle first and last# bits of a numberfrom math import log# Function to toggle first and last bits# of a numberdef toggleFandLbits(n): # calculating mask mask = 2 ** (int(log(n, 2))) + 1 # taking xor of mask and n return mask ^ n# Driver coden = 10# Function callprint(toggleFandLbits(n))# This code is contributed by phasing17 |
C#
// C# program to toggle first and last// bits of a numberusing System;class GFG { // function to toggle first and last bits // of a number static int toggleFandLbits(int n) { // calculating mask int mask = (int)Math.Pow( 2, (int)(Math.Log(n) / Math.Log(2))) + 1; // taking xor of mask and n return mask ^ n; } // Driver code public static void Main(string[] args) { int n = 10; // Function call Console.WriteLine(toggleFandLbits(n)); }}// This code is contributed by phasing17 |
Javascript
// JavaScript program to toggle first and last// bits of a number// function to toggle first and last bits// of a numberfunction toggleFandLbits(n){ // calculating mask let mask = Math.pow(2, Math.floor(Math.log2(n))) + 1; // taking xor of mask and n return mask ^ n;}// Driver codelet n = 10; // function callconsole.log(toggleFandLbits(n));// This code is contributed by phasing17 |
Output
3
Time Complexity: O(log2(log2n)), as pow(log(n)) will be calculated to complexity will be log(log(n)).
Auxiliary Space: O(1).
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
