Tuesday, June 14, 2022
HomeWordPress DevelopmentPlace of rightmost set bit

Place of rightmost set bit


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)

RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

- Advertisment -
Google search engine

Most Popular

Recent Comments