Get the position of rightmost unset bit
Given a non-negative number n. Find the position of rightmost unset bit in the binary representation of n, considering the last bit at position 1, 2nd last bit at position 2 and so on. If no 0’s are there in the binary representation of n. then print “-1”.
Examples:
Input : n = 9 Output : 2 (9)10 = (1001)2 The position of rightmost unset bit in the binary representation of 9 is 2. Input : n = 32 Output : 1
Approach: Following are the steps:
- If n = 0, return 1.
- If all bits of n are set, return -1. Refer this post.
- Else perform bitwise not on the given number(operation equivalent to 1’s complement). Let it be num = ~n.
- Get the position of rightmost set bit of num. This will be the position of rightmost unset bit of n.
C++
// C++ implementation to get the position of rightmost unset bit #include <bits/stdc++.h> using namespace std; // function to find the position // of rightmost set bit int getPosOfRightmostSetBit( int n) { return log2(n&-n)+1; } // function to get the position of rightmost unset bit int getPosOfRightMostUnsetBit( int n) { // if n = 0, return 1 if (n == 0) return 1; // if all bits of 'n' are set if ((n & (n + 1)) == 0) return -1; // position of rightmost unset bit in 'n' // passing ~n as argument return getPosOfRightmostSetBit(~n); } // Driver program to test above int main() { int n = 9; cout << getPosOfRightMostUnsetBit(n); return 0; } |
Java
// Java implementation to get the // position of rightmost unset bit class GFG { // function to find the position // of rightmost set bit static int getPosOfRightmostSetBit( int n) { return ( int )((Math.log10(n & -n)) / Math.log10( 2 )) + 1 ; } // function to get the position // of rightmost unset bit static int getPosOfRightMostUnsetBit( int n) { // if n = 0, return 1 if (n == 0 ) return 1 ; // if all bits of 'n' are set if ((n & (n + 1 )) == 0 ) return - 1 ; // position of rightmost unset bit in 'n' // passing ~n as argument return getPosOfRightmostSetBit(~n); } // Driver code public static void main(String arg[]) { int n = 9 ; System.out.print(getPosOfRightMostUnsetBit(n)); } } // This code is contributed by Anant Agarwal. |
Python3
# Python3 implementation to get the position # of rightmost unset bit # import library import math as m # function to find the position # of rightmost set bit def getPosOfRightmostSetBit(n): return (m.log(((n & - n) + 1 ), 2 )) # function to get the position ot rightmost unset bit def getPosOfRightMostUnsetBit(n): # if n = 0, return 1 if (n = = 0 ): return 1 # if all bits of 'n' are set if ((n & (n + 1 )) = = 0 ): return - 1 # position of rightmost unset bit in 'n' # passing ~n as argument return getPosOfRightmostSetBit(~n) # Driver program to test above n = 13 ; ans = getPosOfRightMostUnsetBit(n) #rounding the final answer print ( round (ans)) # This code is contributed by Saloni Gupta. |
C#
// C# implementation to get the // position of rightmost unset bit using System; class GFG { // function to find the position // of rightmost set bit static int getPosOfRightmostSetBit( int n) { return ( int )((Math.Log10(n & -n)) / Math.Log10(2)) + 1; } // function to get the position // of rightmost unset bit static int getPosOfRightMostUnsetBit( int n) { // if n = 0, return 1 if (n == 0) return 1; // if all bits of 'n' are set if ((n & (n + 1)) == 0) return -1; // position of rightmost unset bit in 'n' // passing ~n as argument return getPosOfRightmostSetBit(~n); } // Driver code public static void Main() { int n = 9; Console.Write(getPosOfRightMostUnsetBit(n)); } } // This code is contributed by Sam007 |
PHP
<?php // PHP implementation to get the // position of rightmost unset bit // function to find the position // of rightmost set bit function getPosOfRightmostSetBit( $n ) { return ceil (log( $n &- $n ) + 1); } // function to get the position // of rightmost unset bit function getPosOfRightMostUnsetBit( $n ) { // if n = 0, return 1 if ( $n == 0) return 1; // if all bits of 'n' are set if (( $n & ( $n + 1)) == 0) return -1; // position of rightmost unset bit in 'n' // passing ~n as argument return getPosOfRightmostSetBit(~ $n ); } // Driver Code $n = 9; echo getPosOfRightMostUnsetBit( $n ); // This code is contributed by anuj_67. ?> |
Javascript
<script> // JavaScript implementation to get the position of rightmost unset bit // function to find the position // of rightmost set bit function getPosOfRightmostSetBit(n) { return Math.log2(n&-n)+1; } // function to get the position of rightmost unset bit function getPosOfRightMostUnsetBit(n) { // if n = 0, return 1 if (n == 0) return 1; // if all bits of 'n' are set if ((n & (n + 1)) == 0) return -1; // position of rightmost unset bit in 'n' // passing ~n as argument return getPosOfRightmostSetBit(~n); } // Driver program to test above let n = 9; document.write(getPosOfRightMostUnsetBit(n)); // This code is contributed by Manoj. </script> |
Output:
2
Time Complexity – O(1)
Space Complexity – O(1)