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 codeint 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 codeint main(){ int n = 18; int ans = log2(n & -n) + 1; printf("%d", ans); getchar(); return 0;} |
Java
// Java Code for Position of rightmost set bitimport 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 bitimport mathdef getFirstSetBitPos(n): return math.log2(n & -n)+1# driver coden = 18print(int(getFirstSetBitPos(n)))# This code is contributed# by Anant Agarwal. |
C#
// C# Code for Position of rightmost set bitusing 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 bitfunction 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 bitfunction 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> |
Output
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 functionint 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 numberimport 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 numberimport math# Function to find rightmost# set bit in given number.def getFirstSetBitPos(n): return int(math.log2(n & -n) + 1)# Driver Codeif __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 numberusing 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> |
Output
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 bitint 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 Codeint main(){ int n = 18; // function call cout << PositionRightmostSetbit(n); return 0;} |
Java
// Java program to find the// first rightmost set bit// using XOR operatorclass 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 bitdef 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 Coden = 18# function callprint(PositionRightmostSetbit(n))# This code is contributed# by Smitha |
C#
// C# program to find the// first rightmost set bit// using XOR operatorusing 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 bitfunction 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 callecho 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> |
Output
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 32int 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 approachpublic 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 approachINT_SIZE = 32def 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 posif __name__ == "__main__": num = 18 pos = Right_most_setbit(num) print(pos)# This code is contributed by ANKITRAI1 |
C#
// C# implementation of above approachusing 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 approachfunction 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 approachlet 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 codelet num = 18;let pos = Right_most_setbit(num);document.write(pos);// This code is contributed by mukesh07</script> |
Output
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 bitint 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 Codeint 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 approachimport 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 bitdef 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 Coden = 18# Function callpos = PositionRightmostSetbit(n)if(pos != -1): print(pos)else: print(0)# This code is contributed by rohitsingh07052. |
C#
// C# program for above approachusing 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 bitfunction 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 codelet n = 18;// Function calllet 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 bitint 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;} |
Output
2
Time Complexity: O(log2n), Traversing through all the bits of N, where at max there are logN bits.
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!
