Write a one-line perform to return the place of the primary 1 from proper to left, within the binary illustration of an Integer.
Examples:
Enter: n = 18
Output: 2
Rationalization: Binary Illustration of 18 is 010010, therefore place of first set bit from proper is 2.
Enter: n = 19
Output: 1
Rationalization: Binary Illustration of 19 is 010011, therefore place of first set bit from proper is 1.
Place of rightmost set bit utilizing two’s complement:
(n&~(n-1)) at all times return the binary quantity containing the rightmost set bit as 1. if N = 12 (1100) then it is going to return 4 (100). Right here log2 will return, the variety of instances we will specific that quantity in an influence of two. For all binary numbers containing solely the rightmost set bit as 1 like 2, 4, 8, 16, 32…. Discover that place of rightmost set bit is at all times equal to log2(Quantity) + 1.
Observe the steps to resolve the given downside:
- Let enter be 12 (1100)
- Take two’s complement of the given no as all bits are reverted besides the primary ‘1’ from proper to left (0100)
- Do a bit-wise & with unique no, this may return no with the required one solely (0100)
- Take the log2 of the no, you’ll get (place – 1) (2)
- Add 1 (3)
Beneath is the implementation of the above method:
C++
#embrace <iostream>
#embrace <math.h>
utilizing namespace std;
class gfg {
public:
unsigned int getFirstSetBitPos(int n)
{
return log2(n & -n) + 1;
}
};
int foremost()
{
gfg g;
int n = 18;
cout << g.getFirstSetBitPos(n);
return 0;
}
|
C
#embrace <math.h>
#embrace <stdio.h>
int foremost()
{
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 foremost(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#
utilizing System;
class GFG {
public static int getFirstSetBitPos(int n)
{
return (int)((Math.Log10(n & -n)) / Math.Log10(2))
+ 1;
}
public static void Primary()
{
int n = 18;
Console.WriteLine(getFirstSetBitPos(n));
}
}
|
PHP
<?php
perform getFirstSetBitPos($n)
{
return ceil(log(($n& -
$n) + 1, 2));
}
$n = 18;
echo getFirstSetBitPos($n);
?>
|
Javascript
<script>
perform getFirstSetBitPos(n)
{
return Math.log2(n & -n) + 1;
}
let g;
let n = 18;
doc.write(getFirstSetBitPos(n));
</script>
|
Time Complexity: O(log2N), Time taken by log2 perform.
Auxiliary Area: O(1)
Place of rightmost set bit utilizing ffs() perform:
ffs() perform returns the index of first least important set bit. The indexing begins in ffs() perform from 1.
Illustration:
Enter: N = 12
Binary Illustration of 12 is 1100
ffs(N) returns the rightmost set bit index which is 3.
Beneath is the implementation of the above method:
C++
#embrace <bits/stdc++.h>
utilizing namespace std;
int getFirstSetBitPos(int n) { return ffs(n); }
int foremost()
{
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 foremost(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#
utilizing System;
public class GFG {
static int getFirstSetBitPos(int n)
{
return (int)((Math.Log10(n & -n)) / Math.Log10(2))
+ 1;
}
public static void Primary(String[] args)
{
int n = 18;
Console.Write(getFirstSetBitPos(n));
}
}
|
Javascript
<script>
perform getFirstSetBitPos(n)
{
return Math.log2(n & -n) + 1;
}
let n = 18;
doc.write( getFirstSetBitPos(n));
</script>
|
Time Complexity: O(log2N), Time taken by ffs() perform.
Auxiliary Area: O(1)
Place of rightmost set bit utilizing & operator:
Observe the steps beneath to resolve the issue:
- Initialize m as 1 as examine its XOR with the bits ranging from the rightmost bit.
- Left shift m by one until we discover the primary set bit
- as the primary set bit offers a quantity once we carry out a & operation with m.
Beneath is the implementation of above method:
C++
#embrace <bits/stdc++.h>
utilizing namespace std;
int PositionRightmostSetbit(int n)
{
if (n == 0)
return 0;
int place = 1;
int m = 1;
whereas (!(n & m)) {
m = m << 1;
place++;
}
return place;
}
int foremost()
{
int n = 18;
cout << PositionRightmostSetbit(n);
return 0;
}
|
Java
class GFG {
static int PositionRightmostSetbit(int n)
{
int place = 1;
int m = 1;
whereas ((n & m) == 0) {
m = m << 1;
place++;
}
return place;
}
public static void foremost(String[] args)
{
int n = 18;
System.out.println(PositionRightmostSetbit(n));
}
}
|
Python3
def PositionRightmostSetbit(n):
place = 1
m = 1
whereas (not(n & m)):
m = m << 1
place += 1
return place
n = 18
print(PositionRightmostSetbit(n))
|
C#
utilizing System;
class GFG {
static int PositionRightmostSetbit(int n)
{
int place = 1;
int m = 1;
whereas ((n & m) == 0) {
m = m << 1;
place++;
}
return place;
}
static public void Primary()
{
int n = 18;
Console.WriteLine(PositionRightmostSetbit(n));
}
}
|
PHP
<?php
perform PositionRightmostSetbit($n)
{
$place = 1;
$m = 1;
whereas (!($n & $m))
{
$m = $m << 1;
$place++;
}
return $place;
}
$n = 18;
echo PositionRightmostSetbit($n);
?>
|
Javascript
<script>
perform PositionRightmostSetbit(n)
{
let place = 1;
let m = 1;
whereas ((n & m) == 0) {
m = m << 1;
place++;
}
return place;
}
let n = 18;
doc.write(PositionRightmostSetbit(n));
</script>
|
Time Complexity: O(log2N), Traversing by all of the bits of N, the place at max there are logN bits.
Auxiliary Area: O(1)
Place of rightmost set bit utilizing Left Shift(<<):
Observe the steps beneath to resolve the issue:
- Initialize pos with 1
- iterate as much as INT_SIZE(Right here 32)
- examine whether or not bit is about or not
- if bit is about then break the loop
- else increment the pos.
Beneath is the implementation of the above method:
C++
#embrace <iostream>
utilizing namespace std;
#outline 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 foremost()
{
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 foremost(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 vary(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#
utilizing 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 Primary()
{
int num = 18;
int pos = Right_most_setbit(num);
Console.WriteLine(pos);
}
}
|
PHP
<?php
perform 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;
perform 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);
doc.write(pos);
</script>
|
Time Complexity: O(log2n), Traversing by all of the bits of N, the place at max there are logN bits.
Auxiliary Area: O(1)
Place of rightmost set bit utilizing Proper Shift(>>):
Observe the steps beneath to resolve the issue:
- Initialize pos=1.
- Iterate until quantity>0, at every step examine if the final bit is about.
- If final bit is about, return present place
- else increment pos by 1 and proper shift n by 1.
Beneath is the implementation of the above method:
C++
#embrace <bits/stdc++.h>
utilizing namespace std;
int PositionRightmostSetbit(int n)
{
int p = 1;
whereas (n > 0) {
if (n & 1) {
return p;
}
p++;
n = n >> 1;
}
return -1;
}
int foremost()
{
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;
whereas (n > 0) {
if ((n & 1) > 0) {
return p;
}
p++;
n = n >> 1;
}
return -1;
}
public static void foremost(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
whereas(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#
utilizing System;
class GFG {
public static int Last_set_bit(int n)
{
int p = 1;
whereas (n > 0) {
if ((n & 1) > 0) {
return p;
}
p++;
n = n >> 1;
}
return -1;
}
public static void Primary(string[] args)
{
int n = 18;
int pos = Last_set_bit(n);
if (pos != -1)
Console.WriteLine(pos);
else
Console.WriteLine("0");
}
}
|
Javascript
<script>
perform Last_set_bit(n)
{
let p = 1;
whereas (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)
{
doc.write(pos);
}
else
{
doc.write(0);
}
</script>
|
C
#embrace <stdio.h>
int Last_set_bit(int n)
{
int p = 1;
whereas (n > 0) {
if ((n & 1) > 0) {
return p;
}
p++;
n = n >> 1;
}
return -1;
}
int foremost(void)
{
int n = 18;
int pos = Last_set_bit(n);
if (pos != -1)
printf("%dn", pos);
else
printf("0n");
return 0;
}
|
Time Complexity: O(log2n), Traversing by all of the bits of N, the place at max there are logN bits.
Auxiliary Area: O(1)
