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>

Output

Time Complexity: O(log₂N), Time taken by log2 function.
Auxiliary Space: O(1)