Position of rightmost set bit using two’s complement
(n&~(n-1)) always return the binary number containing the rightmost set bit as 1. if N = 12 (1100) then it will return 4 (100). Here log2 will return, the number of times we can express that number in a power of two. For all binary numbers containing only the rightmost set bit as 1 like 2, 4, 8, 16, 32…. Find that position of rightmost set bit is always equal to log2(Number) + 1.
Follow the steps to solve the given problem:
- Let input be 12 (1100)
- Take two’s complement of the given no as all bits are reverted except the first ‘1’ from right to left (0100)
- Do a bit-wise & with original no, this will return no with the required one only (0100)
- Take the log2 of the no, you will get (position – 1) (2)
- Add 1 (3)
Below is the implementation of the above approach:
C++
// C++ program for Position // of rightmost set bit #include <iostream> #include <math.h> using namespace std; class gfg { public : unsigned int getFirstSetBitPos( int n) { return log2(n & -n) + 1; } }; // Driver code int main() { gfg g; int n = 18; cout << g.getFirstSetBitPos(n); return 0; } // This code is contributed by SoM15242 |
C
// C program for Position // of rightmost set bit #include <math.h> #include <stdio.h> // Driver code int main() { int n = 18; int ans = log2(n & -n) + 1; printf ( "%d" , ans); getchar (); return 0; } |
Java
// Java Code for Position of rightmost set bit import java.io.*; class GFG { public static int getFirstSetBitPos( int n) { return ( int )((Math.log10(n & -n)) / Math.log10( 2 )) + 1 ; } // Drive code public static void main(String[] args) { int n = 18 ; System.out.println(getFirstSetBitPos(n)); } } // This code is contributed by Arnav Kr. Mandal |
Python3
# Python Code for Position # of rightmost set bit import math def getFirstSetBitPos(n): return math.log2(n & - n) + 1 # driver code n = 18 print ( int (getFirstSetBitPos(n))) # This code is contributed # by Anant Agarwal. |
C#
// C# Code for Position of rightmost set bit using System; class GFG { public static int getFirstSetBitPos( int n) { return ( int )((Math.Log10(n & -n)) / Math.Log10(2)) + 1; } // Driver method public static void Main() { int n = 18; Console.WriteLine(getFirstSetBitPos(n)); } } // This code is contributed by Sam007 |
PHP
<?php // PHP Code for Position of // rightmost set bit function getFirstSetBitPos( $n ) { return ceil (log(( $n & - $n ) + 1, 2)); } // Driver Code $n = 18; echo getFirstSetBitPos( $n ); // This code is contributed by m_kit ?> |
Javascript
<script> // JavaScript program for Position // of rightmost set bit function getFirstSetBitPos(n) { return Math.log2(n & -n) + 1; } // Driver code let g; let n = 18; document.write(getFirstSetBitPos(n)); // This code is contributed by Manoj. </script> |
2
Time Complexity: O(log2N), Time taken by log2 function.
Auxiliary Space: O(1)
Position of rightmost set bit
Write a one-line function to return the position of the first 1 from right to left, in the binary representation of an Integer.
Examples:
Input: n = 18
Output: 2
Explanation: Binary Representation of 18 is 010010, hence position of first set bit from right is 2.Input: n = 19
Output: 1
Explanation: Binary Representation of 19 is 010011, hence position of first set bit from right is 1.