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++
#include <iostream>
#include <math.h>
using namespace std;
class gfg {
public:
unsigned int getFirstSetBitPos(int n)
{
return log2(n & -n) + 1;
}
};
int main()
{
gfg g;
int n = 18;
cout << g.getFirstSetBitPos(n);
return 0;
}
|
C
#include <math.h>
#include <stdio.h>
int main()
{
int n = 18;
int ans = log2(n & -n) + 1;
printf("%d", ans);
getchar();
return 0;
}
|
Java
import java.io.*;
class GFG {
public static int getFirstSetBitPos(int n)
{
return (int)((Math.log10(n & -n)) / Math.log10(2))
+ 1;
}
public static void main(String[] args)
{
int n = 18;
System.out.println(getFirstSetBitPos(n));
}
}
|
Python3
import math
def getFirstSetBitPos(n):
return math.log2(n & -n)+1
n = 18
print(int(getFirstSetBitPos(n)))
|
C#
using System;
class GFG {
public static int getFirstSetBitPos(int n)
{
return (int)((Math.Log10(n & -n)) / Math.Log10(2))
+ 1;
}
public static void Main()
{
int n = 18;
Console.WriteLine(getFirstSetBitPos(n));
}
}
|
PHP
<?php
function getFirstSetBitPos($n)
{
return ceil(log(($n& -
$n) + 1, 2));
}
$n = 18;
echo getFirstSetBitPos($n);
?>
|
Javascript
<script>
function getFirstSetBitPos(n)
{
return Math.log2(n & -n) + 1;
}
let g;
let n = 18;
document.write(getFirstSetBitPos(n));
</script>
|
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++
#include <bits/stdc++.h>
using namespace std;
int getFirstSetBitPos(int n) { return ffs(n); }
int main()
{
int n = 18;
cout << getFirstSetBitPos(n) << endl;
return 0;
}
|
Java
import java.util.*;
class GFG {
static int getFirstSetBitPos(int n)
{
return (int)((Math.log10(n & -n)) / Math.log10(2))
+ 1;
}
public static void main(String[] args)
{
int n = 18;
System.out.print(getFirstSetBitPos(n));
}
}
|
Python3
import math
def getFirstSetBitPos(n):
return int(math.log2(n & -n) + 1)
if __name__ == '__main__':
n = 18
print(getFirstSetBitPos(n))
|
C#
using System;
public class GFG {
static int getFirstSetBitPos(int n)
{
return (int)((Math.Log10(n & -n)) / Math.Log10(2))
+ 1;
}
public static void Main(String[] args)
{
int n = 18;
Console.Write(getFirstSetBitPos(n));
}
}
|
Javascript
<script>
function getFirstSetBitPos(n)
{
return Math.log2(n & -n) + 1;
}
let n = 18;
document.write( getFirstSetBitPos(n));
</script>
|
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++
#include <bits/stdc++.h>
using namespace std;
int PositionRightmostSetbit(int n)
{
if (n == 0)
return 0;
int position = 1;
int m = 1;
while (!(n & m)) {
m = m << 1;
position++;
}
return position;
}
int main()
{
int n = 18;
cout << PositionRightmostSetbit(n);
return 0;
}
|
Java
class GFG {
static int PositionRightmostSetbit(int n)
{
int position = 1;
int m = 1;
while ((n & m) == 0) {
m = m << 1;
position++;
}
return position;
}
public static void main(String[] args)
{
int n = 18;
System.out.println(PositionRightmostSetbit(n));
}
}
|
Python3
def PositionRightmostSetbit(n):
position = 1
m = 1
while (not(n & m)):
m = m << 1
position += 1
return position
n = 18
print(PositionRightmostSetbit(n))
|
C#
using System;
class GFG {
static int PositionRightmostSetbit(int n)
{
int position = 1;
int m = 1;
while ((n & m) == 0) {
m = m << 1;
position++;
}
return position;
}
static public void Main()
{
int n = 18;
Console.WriteLine(PositionRightmostSetbit(n));
}
}
|
PHP
<?php
function PositionRightmostSetbit($n)
{
$position = 1;
$m = 1;
while (!($n & $m))
{
$m = $m << 1;
$position++;
}
return $position;
}
$n = 18;
echo PositionRightmostSetbit($n);
?>
|
Javascript
<script>
function PositionRightmostSetbit(n)
{
let position = 1;
let m = 1;
while ((n & m) == 0) {
m = m << 1;
position++;
}
return position;
}
let n = 18;
document.write(PositionRightmostSetbit(n));
</script>
|
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++
#include <iostream>
using namespace std;
#define INT_SIZE 32
int Right_most_setbit(int num)
{
if (num == 0)
{
return 0;
}
else {
int pos = 1;
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;
}
|
Java
public class GFG {
static int INT_SIZE = 32;
static int Right_most_setbit(int num)
{
int pos = 1;
for (int i = 0; i < INT_SIZE; i++) {
if ((num & (1 << i)) == 0)
pos++;
else
break;
}
return pos;
}
public static void main(String[] args)
{
int num = 18;
int pos = Right_most_setbit(num);
System.out.println(pos);
}
}
|
Python3
INT_SIZE = 32
def Right_most_setbit(num):
pos = 1
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)
|
C#
using System;
class GFG {
static int INT_SIZE = 32;
static int Right_most_setbit(int num)
{
int pos = 1;
for (int i = 0; i < INT_SIZE; i++) {
if ((num & (1 << i)) == 0)
pos++;
else
break;
}
return pos;
}
static public void Main()
{
int num = 18;
int pos = Right_most_setbit(num);
Console.WriteLine(pos);
}
}
|
PHP
<?php
function Right_most_setbit($num)
{
$pos = 1;
$INT_SIZE = 32;
for ($i = 0; $i < $INT_SIZE; $i++)
{
if (!($num & (1 << $i)))
$pos++;
else
break;
}
return $pos;
}
$num = 18;
$pos = Right_most_setbit($num);
echo $pos;
echo ("\n")
?>
|
Javascript
<script>
let INT_SIZE = 32;
function Right_most_setbit(num)
{
let pos = 1;
for(let i = 0; i < INT_SIZE; i++)
{
if ((num & (1 << i)) == 0)
pos++;
else
break;
}
return pos;
}
let num = 18;
let pos = Right_most_setbit(num);
document.write(pos);
</script>
|
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++
#include <bits/stdc++.h>
using namespace std;
int PositionRightmostSetbit(int n)
{
int p = 1;
while (n > 0) {
if (n & 1) {
return p;
}
p++;
n = n >> 1;
}
return -1;
}
int main()
{
int n = 18;
int pos = PositionRightmostSetbit(n);
if (pos != -1)
cout << pos;
else
cout << 0;
return 0;
}
|
Java
import java.io.*;
class GFG {
public static int Last_set_bit(int n)
{
int p = 1;
while (n > 0) {
if ((n & 1) > 0) {
return p;
}
p++;
n = n >> 1;
}
return -1;
}
public static void main(String[] args)
{
int n = 18;
int pos = Last_set_bit(n);
if (pos != -1)
System.out.println(pos);
else
System.out.println("0");
}
}
|
Python3
def PositionRightmostSetbit(n):
p = 1
while(n > 0):
if(n & 1):
return p
p += 1
n = n >> 1
return -1
n = 18
pos = PositionRightmostSetbit(n)
if(pos != -1):
print(pos)
else:
print(0)
|
C#
using System;
class GFG {
public static int Last_set_bit(int n)
{
int p = 1;
while (n > 0) {
if ((n & 1) > 0) {
return p;
}
p++;
n = n >> 1;
}
return -1;
}
public static void Main(string[] args)
{
int n = 18;
int pos = Last_set_bit(n);
if (pos != -1)
Console.WriteLine(pos);
else
Console.WriteLine("0");
}
}
|
Javascript
<script>
function Last_set_bit(n)
{
let p = 1;
while (n > 0)
{
if ((n & 1) > 0)
{
return p;
}
p++;
n = n >> 1;
}
return -1;
}
let n = 18;
let pos = Last_set_bit(n);
if (pos != -1)
{
document.write(pos);
}
else
{
document.write(0);
}
</script>
|
C
#include <stdio.h>
int Last_set_bit(int n)
{
int p = 1;
while (n > 0) {
if ((n & 1) > 0) {
return p;
}
p++;
n = n >> 1;
}
return -1;
}
int main(void)
{
int n = 18;
int pos = Last_set_bit(n);
if (pos != -1)
printf("%d\n", pos);
else
printf("0\n");
return 0;
}
|
Time Complexity: O(log2n), Traversing through all the bits of N, where at max there are logN bits.
Auxiliary Space: O(1)
