Write a one-line operate to return the place of the primary 1 from proper to left, within the binary illustration of an Integer.
I/P 18, Binary Illustration 010010
O/P 2
I/P 19, Binary Illustration 010011
O/P 1
Algorithm: (Instance 12(1100))
Let I/P be 12 (1100)
1. Take two’s complement of the given no as all bits are reverted
besides the primary ‘1’ from proper to left (0100)
2 Do a bit-wise & with unique no, this may return no with the
required one solely (0100)
3 Take the log2 of the no, you’re going to get (place – 1) (2)
4 Add 1 (3)
Clarification –
(n&~(n-1)) at all times 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 you, the variety of instances we will categorical 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….
We’ll discover that place of rightmost set bit is at all times equal to log2(Quantity)+1
Program:
C++
#embody <iostream>
#embody <math.h>
utilizing namespace std;
class gfg
{
public :
unsigned int getFirstSetBitPos( int n)
{
return log2(n & -n) + 1;
}
};
int primary()
{
gfg g;
int n = 12;
cout << g.getFirstSetBitPos(n);
return 0;
}
|
C
#embody <math.h>
#embody <stdio.h>
unsigned int getFirstSetBitPos( int n)
{
return log2(n & -n) + 1;
}
int primary()
{
int n = 12;
printf ( "%u" , getFirstSetBitPos(n));
getchar ();
return 0;
}
|
Java
class GFG {
public static int getFirstSetBitPos( int n)
{
return ( int )((Math.log10(n & -n)) / Math.log10( 2 )) + 1 ;
}
public static void primary(String[] args)
{
int n = 12 ;
System.out.println(getFirstSetBitPos(n));
}
}
|
Python3
import math
def getFirstSetBitPos(n):
return math.log2(n& - n) + 1
n = 12
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 Principal()
{
int n = 12;
Console.WriteLine(getFirstSetBitPos(n));
}
}
|
PHP
<?php
operate getFirstSetBitPos( $n )
{
return ceil (log(( $n & -
$n ) + 1, 2));
}
$n = 12;
echo getFirstSetBitPos( $n );
?>
|
Javascript
<script>
operate getFirstSetBitPos(n)
{
return Math.log2(n & -n) + 1;
}
let g;
let n = 12;
doc.write(getFirstSetBitPos(n));
</script>
|
Time Complexity: O(log2n)
Auxiliary Area: O(1)
Utilizing ffs() operate: ffs() operate returns the index of first least vital set bit. The indexing begins in ffs() operate from 1.
For instance:
n = 12 = 1100
Within the above instance, ffs(n) returns the rightmost set bit index which is 3.
C++
#embody <bits/stdc++.h>
utilizing namespace std;
int getFirstSetBitPos( int n)
{
return ffs(n);
}
int primary()
{
int n = 12;
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 primary(String[] args)
{
int n = 12 ;
System.out.print( getFirstSetBitPos(n));
}
}
|
Python3
import math
def getFirstSetBitPos(n):
return int (math.log2 (n & - n) + 1 )
if __name__ = = '__main__' :
n = 12
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 Principal(String[] args)
{
int n = 12;
Console.Write( getFirstSetBitPos(n));
}
}
|
Javascript
<script>
operate getFirstSetBitPos(n)
{
return Math.log2(n & -n) + 1;
}
let n = 12;
doc.write( getFirstSetBitPos(n));
</script>
|
Time Complexity: O(log2n)
Auxiliary Area: O(1)
Utilizing XOR and & operator :
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.
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 primary()
{
int n = 16;
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 primary(String[] args)
{
int n = 16 ;
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 = 16
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 Principal()
{
int n = 16;
Console.WriteLine(
PositionRightmostSetbit(n));
}
}
|
PHP
<?php
operate PositionRightmostSetbit( $n )
{
$place = 1;
$m = 1;
whereas (!( $n & $m ))
{
$m = $m << 1;
$place ++;
}
return $place ;
}
$n = 16;
echo PositionRightmostSetbit( $n );
?>
|
Javascript
<script>
operate PositionRightmostSetbit(n)
{
let place = 1;
let m = 1;
whereas ((n & m) == 0) {
m = m << 1;
place++;
}
return place;
}
let n = 16;
doc.write(PositionRightmostSetbit(n));
</script>
|
Time Complexity: O(log2n)
Auxiliary Area: O(1)
This method has been contributed by mubashshir ahmad
Utilizing Left Shift (<<) : Initialize pos with 1, iterate as much as INT_SIZE(Right here 32) and examine whether or not bit is ready or not, if bit is ready then break the loop, else increment the pos.
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 primary()
{
int num = 0;
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 primary(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 Principal ()
{
int num = 18;
int pos = Right_most_setbit(num);
Console.WriteLine(pos);
}
}
|
PHP
<?php
operate 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;
operate 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>
|
Output :
2
Time Complexity: O(log2n)
Auxiliary Area: O(1)
One other Methodology Utilizing proper Shift(>>):
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.
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 primary()
{
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 primary(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 Principal( string [] args)
{
int n = 18;
int pos = Last_set_bit(n);
if (pos != -1)
Console.WriteLine(pos);
else
Console.WriteLine( "0" );
}
}
|
Javascript
<script>
operate 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>
|
Time Complexity: O(log2n)
Auxiliary Area: O(1)