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.
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 using ffs() function:
ffs() function returns the index of first least significant set bit. The indexing starts in ffs() function from 1.
Illustration:
Input: N = 12
Binary Representation of 12 is 1100
ffs(N) returns the rightmost set bit index which is 3.
Below is the implementation of the above approach:
C++
// C++ program to find the // position of first rightmost // set bit in a given number. #include <bits/stdc++.h> using namespace std; // Function to find rightmost // set bit in given number. int getFirstSetBitPos( int n) { return ffs(n); } // Driver function int main() { int n = 18; cout << getFirstSetBitPos(n) << endl; return 0; } |
Java
// Java program to find the // position of first rightmost // set bit in a given number import java.util.*; class GFG { // Function to find rightmost // set bit in given number. static int getFirstSetBitPos( int n) { return ( int )((Math.log10(n & -n)) / Math.log10( 2 )) + 1 ; } // Driver code public static void main(String[] args) { int n = 18 ; System.out.print(getFirstSetBitPos(n)); } } // This code is contributed by sanjoy_62. |
Python3
# Python3 program to find the # position of first rightmost # set bit in a given number import math # Function to find rightmost # set bit in given number. def getFirstSetBitPos(n): return int (math.log2(n & - n) + 1 ) # Driver Code if __name__ = = '__main__' : n = 18 print (getFirstSetBitPos(n)) # This code is contributed by nirajgusain5. |
C#
// C# program to find the // position of first rightmost // set bit in a given number using System; public class GFG { // Function to find rightmost // set bit in given number. static int getFirstSetBitPos( int n) { return ( int )((Math.Log10(n & -n)) / Math.Log10(2)) + 1; } // Driver code public static void Main(String[] args) { int n = 18; Console.Write(getFirstSetBitPos(n)); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript program to find the // position of first rightmost // set bit in a given number // Function to find rightmost // set bit in given number. function getFirstSetBitPos(n) { return Math.log2(n & -n) + 1; } // Driver Code let n = 18; document.write( getFirstSetBitPos(n)); </script> |
2
Time Complexity: O(log2N), Time taken by ffs() function.
Auxiliary Space: O(1)
Position of rightmost set bit using & operator:
Follow the steps below to solve the problem:
- Initialize m as 1 as check its XOR with the bits starting from the rightmost bit.
- Left shift m by one till we find the first set bit
- as the first set bit gives a number when we perform a & operation with m.
Below is the implementation of above approach:
C++
// C++ program to find the first // rightmost set bit using XOR operator #include <bits/stdc++.h> using namespace std; // function to find the rightmost set bit int PositionRightmostSetbit( int n) { if (n == 0) return 0; // Position variable initialize with 1 // m variable is used to check the set bit int position = 1; int m = 1; while (!(n & m)) { // left shift m = m << 1; position++; } return position; } // Driver Code int main() { int n = 18; // function call cout << PositionRightmostSetbit(n); return 0; } |
Java
// Java program to find the // first rightmost set bit // using XOR operator class GFG { // function to find // the rightmost set bit static int PositionRightmostSetbit( int n) { // Position variable initialize // with 1 m variable is used to // check the set bit int position = 1 ; int m = 1 ; while ((n & m) == 0 ) { // left shift m = m << 1 ; position++; } return position; } // Driver Code public static void main(String[] args) { int n = 18 ; // function call System.out.println(PositionRightmostSetbit(n)); } } // This code is contributed // by Smitha |
Python3
# Python3 program to find # the first rightmost set # bit using XOR operator # function to find the # rightmost set bit def PositionRightmostSetbit(n): # Position variable initialize # with 1 m variable is used # to check the set bit position = 1 m = 1 while ( not (n & m)): # left shift m = m << 1 position + = 1 return position # Driver Code n = 18 # function call print (PositionRightmostSetbit(n)) # This code is contributed # by Smitha |
C#
// C# program to find the // first rightmost set bit // using XOR operator using System; class GFG { // function to find // the rightmost set bit static int PositionRightmostSetbit( int n) { // Position variable initialize // with 1 m variable is used to // check the set bit int position = 1; int m = 1; while ((n & m) == 0) { // left shift m = m << 1; position++; } return position; } // Driver Code static public void Main() { int n = 18; // function call Console.WriteLine(PositionRightmostSetbit(n)); } } // This code is contributed // by @ajit |
PHP
<?php // PHP program to find the // first rightmost set bit // using XOR operator // function to find the // rightmost set bit function PositionRightmostSetbit( $n ) { // Position variable initialize // with 1 m variable is used to // check the set bit $position = 1; $m = 1; while (!( $n & $m )) { // left shift $m = $m << 1; $position ++; } return $position ; } // Driver Code $n = 18; // function call echo PositionRightmostSetbit( $n ); // This code is contributed by ajit ?> |
Javascript
<script> // Javascript program to find the first // rightmost set bit using XOR operator // function to find the rightmost set bit function PositionRightmostSetbit(n) { // Position variable initialize with 1 // m variable is used to check the set bit let position = 1; let m = 1; while ((n & m) == 0) { // left shift m = m << 1; position++; } return position; } let n = 18; // function call document.write(PositionRightmostSetbit(n)); // This code is contributed by divyesh072019. </script> |
2
Time Complexity: O(log2N), Traversing through all the bits of N, where at max there are logN bits.
Auxiliary Space: O(1)
Position of rightmost set bit using Left Shift(<<):
Follow the steps below to solve the problem:
- Initialize pos with 1
- iterate up to INT_SIZE(Here 32)
- check whether bit is set or not
- if bit is set then break the loop
- else increment the pos.
Below is the implementation of the above approach:
C++
// C++ implementation of above approach #include <iostream> using namespace std; #define INT_SIZE 32 int Right_most_setbit( int num) { if (num == 0) // for num==0 there is zero set bit { return 0; } else { int pos = 1; // counting the position of first set bit for ( int i = 0; i < INT_SIZE; i++) { if (!(num & (1 << i))) pos++; else break ; } return pos; } } int main() { int num = 18; int pos = Right_most_setbit(num); cout << pos << endl; return 0; } // This approach has been contributed by @yashasvi7 |
Java
// Java implementation of above approach public class GFG { static int INT_SIZE = 32 ; static int Right_most_setbit( int num) { int pos = 1 ; // counting the position of first set bit for ( int i = 0 ; i < INT_SIZE; i++) { if ((num & ( 1 << i)) == 0 ) pos++; else break ; } return pos; } // Driver code public static void main(String[] args) { int num = 18 ; int pos = Right_most_setbit(num); System.out.println(pos); } } |
Python3
# Python 3 implementation of above approach INT_SIZE = 32 def Right_most_setbit(num): pos = 1 # counting the position of first set bit for i in range (INT_SIZE): if not (num & ( 1 << i)): pos + = 1 else : break return pos if __name__ = = "__main__" : num = 18 pos = Right_most_setbit(num) print (pos) # This code is contributed by ANKITRAI1 |
C#
// C# implementation of above approach using System; class GFG { static int INT_SIZE = 32; static int Right_most_setbit( int num) { int pos = 1; // counting the position // of first set bit for ( int i = 0; i < INT_SIZE; i++) { if ((num & (1 << i)) == 0) pos++; else break ; } return pos; } // Driver code static public void Main() { int num = 18; int pos = Right_most_setbit(num); Console.WriteLine(pos); } } |
PHP
<?php // PHP implementation of above approach function Right_most_setbit( $num ) { $pos = 1; $INT_SIZE = 32; // counting the position // of first set bit for ( $i = 0; $i < $INT_SIZE ; $i ++) { if (!( $num & (1 << $i ))) $pos ++; else break ; } return $pos ; } // Driver code $num = 18; $pos = Right_most_setbit( $num ); echo $pos ; echo ( "\n" ) // This code is contributed // by Shivi_Aggarwal ?> |
Javascript
<script> // Javascript implementation of above approach let INT_SIZE = 32; function Right_most_setbit(num) { let pos = 1; // Counting the position of first set bit for (let i = 0; i < INT_SIZE; i++) { if ((num & (1 << i)) == 0) pos++; else break ; } return pos; } // Driver code let num = 18; let pos = Right_most_setbit(num); document.write(pos); // This code is contributed by mukesh07 </script> |
2
Time Complexity: O(log2n), Traversing through all the bits of N, where at max there are logN bits.
Auxiliary Space: O(1)
Position of rightmost set bit using Right Shift(>>):
Follow the steps below to solve the problem:
- Initialize pos=1.
- Iterate till number>0, at each step check if the last bit is set.
- If last bit is set, return current position
- else increment pos by 1 and right shift n by 1.
Below is the implementation of the above approach:
C++
// C++ program for above approach #include <bits/stdc++.h> using namespace std; // Program to find position of // rightmost set bit int PositionRightmostSetbit( int n) { int p = 1; // Iterate till number>0 while (n > 0) { // Checking if last bit is set if (n & 1) { return p; } // Increment position and right shift number p++; n = n >> 1; } // set bit not found. return -1; } // Driver Code int main() { int n = 18; // Function call int pos = PositionRightmostSetbit(n); if (pos != -1) cout << pos; else cout << 0; return 0; } // This code is contributed by zishanahmad786 |
Java
// Java program for above approach import java.io.*; class GFG { // Function to find position of // rightmost set bit public static int Last_set_bit( int n) { int p = 1 ; // Iterate till number>0 while (n > 0 ) { // Checking if last bit is set if ((n & 1 ) > 0 ) { return p; } // Increment position and // right shift number p++; n = n >> 1 ; } // set bit not found. return - 1 ; } // Driver Code public static void main(String[] args) { int n = 18 ; // Function call int pos = Last_set_bit(n); if (pos != - 1 ) System.out.println(pos); else System.out.println( "0" ); } } // This code is contributed by RohitOberoi |
Python3
# Python program for above approach # Program to find position of # rightmost set bit def PositionRightmostSetbit(n): p = 1 # Iterate till number>0 while (n > 0 ): # Checking if last bit is set if (n & 1 ): return p # Increment position and right shift number p + = 1 n = n >> 1 # set bit not found. return - 1 # Driver Code n = 18 # Function call pos = PositionRightmostSetbit(n) if (pos ! = - 1 ): print (pos) else : print ( 0 ) # This code is contributed by rohitsingh07052. |
C#
// C# program for above approach using System; class GFG { // Function to find position of // rightmost set bit public static int Last_set_bit( int n) { int p = 1; // Iterate till number>0 while (n > 0) { // Checking if last bit is set if ((n & 1) > 0) { return p; } // Increment position and // right shift number p++; n = n >> 1; } // Set bit not found. return -1; } // Driver Code public static void Main( string [] args) { int n = 18; // Function call int pos = Last_set_bit(n); if (pos != -1) Console.WriteLine(pos); else Console.WriteLine( "0" ); } } // This code is contributed by AnkThon |
Javascript
<script> // Javascript program for above approach // Program to find position of // rightmost set bit function Last_set_bit(n) { let p = 1; // Iterate till number>0 while (n > 0) { // Checking if last bit is set if ((n & 1) > 0) { return p; } // Increment position and // right shift number p++; n = n >> 1; } // Set bit not found. return -1; } // Driver code let n = 18; // Function call let pos = Last_set_bit(n); if (pos != -1) { document.write(pos); } else { document.write(0); } // This code is contributed by divyeshrabadiya07 </script> |
C
#include <stdio.h> // Function to find position of // rightmost set bit int Last_set_bit( int n) { int p = 1; // Iterate till number>0 while (n > 0) { // Checking if last bit is set if ((n & 1) > 0) { return p; } // Increment position and // right shift number p++; n = n >> 1; } // set bit not found. return -1; } int main( void ) { int n = 18; // Function call int pos = Last_set_bit(n); if (pos != -1) printf ( "%d\n" , pos); else printf ( "0\n" ); return 0; } |
2
Time Complexity: O(log2n), Traversing through all the bits of N, where at max there are logN bits.
Auxiliary Space: O(1)