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)) all the time return the binary quantity containing the rightmost set bit as 1. if N = 12 (1100) then it can return 4 (100). Right here log2 will return, the variety of occasions we are able to 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 all the time equal to log2(Quantity) + 1.
Observe the steps to unravel 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’re going to get (place – 1) (2)
- Add 1 (3)
Beneath is the implementation of the above strategy:
C++
#embody <iostream>
#embody <math.h>
utilizing namespace std;
class gfg {
public:
unsigned int getFirstSetBitPos(int n)
{
return log2(n & -n) + 1;
}
};
int predominant()
{
gfg g;
int n = 18;
cout << g.getFirstSetBitPos(n);
return 0;
}
|
C
#embody <math.h>
#embody <stdio.h>
int predominant()
{
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 predominant(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 Essential()
{
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 strategy:
C++
#embody <bits/stdc++.h>
utilizing namespace std;
int getFirstSetBitPos(int n) { return ffs(n); }
int predominant()
{
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 predominant(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 Essential(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 unravel 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 after we carry out a & operation with m.
Beneath is the implementation of above strategy:
C++
#embody <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 predominant()
{
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 predominant(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 Essential()
{
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 unravel the issue:
- Initialize pos with 1
- iterate as much as INT_SIZE(Right here 32)
- examine whether or not bit is ready or not
- if bit is ready then break the loop
- else increment the pos.
Beneath is the implementation of the above strategy:
C++
#embody <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 predominant()
{
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 predominant(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 Essential()
{
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 unravel the issue:
- Initialize pos=1.
- Iterate until quantity>0, at every step examine if the final bit is ready.
- If final bit is ready, return present place
- else increment pos by 1 and proper shift n by 1.
Beneath is the implementation of the above strategy:
C++
#embody <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 predominant()
{
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 predominant(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 Essential(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
#embody <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 predominant(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)
