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 bitint getPosOfRightmostSetBit(int n){ return log2(n&-n)+1;}// function to get the position of rightmost unset bitint 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 aboveint main(){ int n = 9; cout << getPosOfRightMostUnsetBit(n); return 0;} |
Java
// Java implementation to get the// position of rightmost unset bitclass GFG { // function to find the position// of rightmost set bitstatic int getPosOfRightmostSetBit(int n) { return (int)((Math.log10(n & -n)) / Math.log10(2)) + 1;}// function to get the position// of rightmost unset bitstatic 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 codepublic 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 libraryimport math as m # function to find the position # of rightmost set bitdef getPosOfRightmostSetBit(n): return (m.log(((n & - n) + 1),2)) # function to get the position ot rightmost unset bitdef 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 aboven = 13;ans = getPosOfRightMostUnsetBit(n)#rounding the final answerprint (round(ans))# This code is contributed by Saloni Gupta. |
C#
// C# implementation to get the// position of rightmost unset bitusing 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 bitfunction getPosOfRightmostSetBit( $n){ return ceil(log($n &- $n) + 1);}// function to get the position // of rightmost unset bitfunction 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 bitfunction getPosOfRightmostSetBit(n){ return Math.log2(n&-n)+1;}// function to get the position of rightmost unset bitfunction 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)
This article is contributed by Ayush Jauhari. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
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!
