Place of rightmost set bit

Software Development

Place of rightmost set bit

lohitnath.453

August 24, 2023

[ad_1]

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
Clarification: Binary Illustration of 18 is 010010, therefore place of first set bit from proper is 2.

Enter: n = 19
Output: 1
Clarification: 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 should return 4 (100). Right here log2 will return, the variety of occasions 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…. Discover that place of rightmost set bit is at all times equal to log2(Quantity) + 1.

Observe the steps to unravel the given drawback:

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)

Under 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 important()

{

gfg g;

int n = 18;

cout << g.getFirstSetBitPos(n);

return 0;

}

C

#embody <math.h>

#embody <stdio.h>

int important()

{

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 important(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 Most important()

{

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(log₂N), Time taken by log2 perform.
Auxiliary House: 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.

Under is the implementation of the above strategy:

C++

#embody <bits/stdc++.h>

utilizing namespace std;

int getFirstSetBitPos(int n) { return ffs(n); }

int important()

{

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 important(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 Most important(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(log₂N), Time taken by ffs() perform.
Auxiliary House: O(1)

Place of rightmost set bit utilizing & operator:

Observe the steps under to unravel the issue:

Initialize m as 1 as verify 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.

Under 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 important()

{

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 important(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 Most important()

{

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(log₂N), Traversing by means of all of the bits of N, the place at max there are logN bits.
Auxiliary House: O(1)

Place of rightmost set bit utilizing Left Shift(<<):

Observe the steps under to unravel the issue:

Initialize pos with 1
iterate as much as INT_SIZE(Right here 32)
verify whether or not bit is about or not
if bit is about then break the loop
else increment the pos.

Under 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 important()

{

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 important(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 Most important()

{

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(log₂n), Traversing by means of all of the bits of N, the place at max there are logN bits.
Auxiliary House: O(1)

Place of rightmost set bit utilizing Proper Shift(>>):

Observe the steps under to unravel the issue:

Initialize pos=1.
Iterate until quantity>0, at every step verify 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.

Under 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 important()

{

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 important(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 Most important(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 important(void)

{

int n = 18;

int pos = Last_set_bit(n);

if (pos != -1)

printf("%dn", pos);

else

printf("0n");

return 0;

}

Time Complexity: O(log₂n), Traversing by means of all of the bits of N, the place at max there are logN bits.
Auxiliary House: O(1)

Final Up to date :
14 Apr, 2023

Like Article