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
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.