Escriba una función de una línea para devolver la posición del primer 1 de derecha a izquierda, en la representación binaria de un entero.
I/P 18, Binary Representation 010010 O/P 2 I/P 19, Binary Representation 010011 O/P 1
Algoritmo: (Ejemplo 12(1100))
Sea I/P 12 (1100)
1. Tome el complemento a dos del no dado ya que todos los bits se revierten
excepto el primer ‘1’ de derecha a izquierda (0100)
2 Haga un bit- inteligente y con el no original, este devolverá el no con el
requerido solo (0100)
3 Tome el log2 del no, obtendrá (posición – 1) (2)
4 Sume 1 (3)
Explicación –
(n&~(n-1)) siempre devuelve el número binario que contiene el bit establecido más a la derecha como 1.
si N = 12 (1100) entonces devolverá 4 (100)
Aquí log2 le devolverá, la cantidad de veces que podemos expresar ese número en una potencia de dos.
Para todos los números binarios que contienen solo el bit más a la derecha establecido como 1 como 2, 4, 8, 16, 32….
Encontraremos que la posición del bit establecido más a la derecha siempre es igual a log2 (Número) + 1
Programa:
C++
// C++ program for Position
// of rightmost set bit
#include <iostream>
#include <math.h>
using namespace std;
class gfg
{
public:
unsigned int getFirstSetBitPos(int n)
{
return log2(n & -n) + 1;
}
};
// Driver code
int main()
{
gfg g;
int n = 12;
cout << g.getFirstSetBitPos(n);
return 0;
}
// This code is contributed by SoM15242
C
// C program for Position
// of rightmost set bit
#include <math.h>
#include <stdio.h>
unsigned int getFirstSetBitPos(int n)
{
return log2(n & -n) + 1;
}
// Driver code
int main()
{
int n = 12;
printf("%u", getFirstSetBitPos(n));
getchar();
return 0;
}
Java
// Java Code for Position of rightmost set bit
class GFG {
public static int getFirstSetBitPos(int n)
{
return (int)((Math.log10(n & -n)) / Math.log10(2)) + 1;
}
// Drive code
public static void main(String[] args)
{
int n = 12;
System.out.println(getFirstSetBitPos(n));
}
}
// This code is contributed by Arnav Kr. Mandal
Python3
# Python Code for Position # of rightmost set bit import math def getFirstSetBitPos(n): return math.log2(n&-n)+1 # driver code n = 12 print(int(getFirstSetBitPos(n))) # This code is contributed # by Anant Agarwal.
C#
// C# Code for Position of rightmost set bit
using System;
class GFG {
public static int getFirstSetBitPos(int n)
{
return (int)((Math.Log10(n & -n))
/ Math.Log10(2)) + 1;
}
// Driver method
public static void Main()
{
int n = 12;
Console.WriteLine(getFirstSetBitPos(n));
}
}
// This code is contributed by Sam007
PHP
<?php
// PHP Code for Position of
// rightmost set bit
function getFirstSetBitPos($n)
{
return ceil(log(($n& -
$n) + 1, 2));
}
// Driver Code
$n = 12;
echo getFirstSetBitPos($n);
// This code is contributed by m_kit
?>
Javascript
<script>
// JavaScript program for Position
// of rightmost set bit
function getFirstSetBitPos(n)
{
return Math.log2(n & -n) + 1;
}
// Driver code
let g;
let n = 12;
document.write(getFirstSetBitPos(n));
// This code is contributed by Manoj.
</script>
Producción
3
Complejidad de tiempo: O( log 2 n )
Espacio auxiliar: O(1)
Uso de la función ffs(): La función ffs() devuelve el índice del primer bit establecido menos significativo. La indexación comienza en la función ffs() desde 1.
Por ejemplo:
n = 12 = 1100
En el ejemplo anterior, ffs(n) devuelve el índice de bits establecido más a la derecha, que es 3.
C++
// C++ program to find the
// position of first rightmost
// set bit in a given number.
#include <bits/stdc++.h>
using namespace std;
// Function to find rightmost
// set bit in given number.
int getFirstSetBitPos(int n)
{
return ffs(n);
}
// Driver function
int main()
{
int n = 12;
cout << getFirstSetBitPos(n) << endl;
return 0;
}
Java
// Java program to find the
// position of first rightmost
// set bit in a given number
import java.util.*;
class GFG{
// Function to find rightmost
// set bit in given number.
static int getFirstSetBitPos(int n)
{
return (int)((Math.log10(n & -n)) / Math.log10(2)) + 1;
}
// Driver code
public static void main(String[] args)
{
int n = 12;
System.out.print( getFirstSetBitPos(n));
}
}
// This code is contributed by sanjoy_62.
Python3
# Python3 program to find the # position of first rightmost # set bit in a given number import math # Function to find rightmost # set bit in given number. def getFirstSetBitPos(n): return int(math.log2 (n & -n) + 1) # Driver Code if __name__ == '__main__': n = 12 print(getFirstSetBitPos(n)) # This code is contributed by nirajgusain5.
C#
// C# program to find the
// position of first rightmost
// set bit in a given number
using System;
public class GFG{
// Function to find rightmost
// set bit in given number.
static int getFirstSetBitPos(int n)
{
return (int)((Math.Log10(n & -n)) / Math.Log10(2)) + 1;
}
// Driver code
public static void Main(String[] args)
{
int n = 12;
Console.Write( getFirstSetBitPos(n));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program to find the
// position of first rightmost
// set bit in a given number
// Function to find rightmost
// set bit in given number.
function getFirstSetBitPos(n)
{
return Math.log2(n & -n) + 1;
}
// Driver Code
let n = 12;
document.write( getFirstSetBitPos(n));
</script>
Producción
3
Complejidad temporal: O(log 2 n)
Espacio auxiliar: O(1)
Usando XOR y el operador &:
Inicialice m como 1 y verifique su XOR con los bits comenzando desde el bit más a la derecha. Desplace m a la izquierda en uno hasta que encontremos el primer bit establecido, ya que el primer bit establecido da un número cuando realizamos una operación & con m.
C++
// C++ program to find the first
// rightmost set bit using XOR operator
#include <bits/stdc++.h>
using namespace std;
// function to find the rightmost set bit
int PositionRightmostSetbit(int n)
{
if(n == 0)
return 0;
// Position variable initialize with 1
// m variable is used to check the set bit
int position = 1;
int m = 1;
while (!(n & m)) {
// left shift
m = m << 1;
position++;
}
return position;
}
// Driver Code
int main()
{
int n = 16;
// function call
cout << PositionRightmostSetbit(n);
return 0;
}
Java
// Java program to find the
// first rightmost set bit
// using XOR operator
class GFG {
// function to find
// the rightmost set bit
static int PositionRightmostSetbit(int n)
{
// Position variable initialize
// with 1 m variable is used to
// check the set bit
int position = 1;
int m = 1;
while ((n & m) == 0) {
// left shift
m = m << 1;
position++;
}
return position;
}
// Driver Code
public static void main(String[] args)
{
int n = 16;
// function call
System.out.println(PositionRightmostSetbit(n));
}
}
// This code is contributed
// by Smitha
Python3
# Python3 program to find # the first rightmost set # bit using XOR operator # function to find the # rightmost set bit def PositionRightmostSetbit(n): # Position variable initialize # with 1 m variable is used # to check the set bit position = 1 m = 1 while (not(n & m)) : # left shift m = m << 1 position += 1 return position # Driver Code n = 16 # function call print(PositionRightmostSetbit(n)) # This code is contributed # by Smitha
C#
// C# program to find the
// first rightmost set bit
// using XOR operator
using System;
class GFG {
// function to find
// the rightmost set bit
static int PositionRightmostSetbit(int n)
{
// Position variable initialize
// with 1 m variable is used to
// check the set bit
int position = 1;
int m = 1;
while ((n & m) == 0) {
// left shift
m = m << 1;
position++;
}
return position;
}
// Driver Code
static public void Main()
{
int n = 16;
// function call
Console.WriteLine(
PositionRightmostSetbit(n));
}
}
// This code is contributed
// by @ajit
PHP
<?php
// PHP program to find the
// first rightmost set bit
// using XOR operator
// function to find the
// rightmost set bit
function PositionRightmostSetbit($n)
{
// Position variable initialize
// with 1 m variable is used to
// check the set bit
$position = 1;
$m = 1;
while (!($n & $m))
{
// left shift
$m = $m << 1;
$position++;
}
return $position;
}
// Driver Code
$n = 16;
// function call
echo PositionRightmostSetbit($n);
// This code is contributed by ajit
?>
Javascript
<script>
// Javascript program to find the first
// rightmost set bit using XOR operator
// function to find the rightmost set bit
function PositionRightmostSetbit(n)
{
// Position variable initialize with 1
// m variable is used to check the set bit
let position = 1;
let m = 1;
while ((n & m) == 0) {
// left shift
m = m << 1;
position++;
}
return position;
}
let n = 16;
// function call
document.write(PositionRightmostSetbit(n));
// This code is contributed by divyesh072019.
</script>
Producción
5
Complejidad temporal: O(log 2 n)
Espacio auxiliar: O(1)
Este enfoque ha sido aportado por mubashshir ahmad
Usando el desplazamiento izquierdo (<<): inicialice pos con 1, itere hasta INT_SIZE (aquí 32) y verifique si el bit está configurado o no, si el bit está configurado, rompa el ciclo, de lo contrario incremente la pos.
C++
// C++ implementation of above approach
#include <iostream>
using namespace std;
#define INT_SIZE 32
int Right_most_setbit(int num)
{
if(num==0)// for num==0 there is zero set bit
{ return 0;
}
else
{
int pos = 1;
// counting the position of first set bit
for (int i = 0; i < INT_SIZE; i++) {
if (!(num & (1 << i)))
pos++;
else
break;
}
return pos;
}
}
int main()
{
int num = 0;
int pos = Right_most_setbit(num);
cout << pos << endl;
return 0;
}
// This approach has been contributed by @yashasvi7
Java
//Java implementation of above approach
public class GFG {
static int INT_SIZE = 32;
static int Right_most_setbit(int num)
{
int pos = 1;
// counting the position of first set bit
for (int i = 0; i < INT_SIZE; i++) {
if ((num & (1 << i))== 0)
pos++;
else
break;
}
return pos;
}
//Driver code
public static void main(String[] args) {
int num = 18;
int pos = Right_most_setbit(num);
System.out.println(pos);
}
}
Python3
# Python 3 implementation of above approach INT_SIZE = 32 def Right_most_setbit(num) : pos = 1 # counting the position of first set bit for i in range(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) # This code is contributed by ANKITRAI1
C#
// C# implementation of above approach
using System;
class GFG {
static int INT_SIZE = 32;
static int Right_most_setbit(int num)
{
int pos = 1;
// counting the position
// of first set bit
for (int i = 0; i < INT_SIZE; i++)
{
if ((num & (1 << i))== 0)
pos++;
else
break;
}
return pos;
}
// Driver code
static public void Main ()
{
int num = 18;
int pos = Right_most_setbit(num);
Console.WriteLine(pos);
}
}
PHP
<?php
// PHP implementation of above approach
function Right_most_setbit($num)
{
$pos = 1;
$INT_SIZE = 32;
// counting the position
// of first set bit
for ($i = 0; $i < $INT_SIZE; $i++)
{
if (!($num & (1 << $i)))
$pos++;
else
break;
}
return $pos;
}
// Driver code
$num = 18;
$pos = Right_most_setbit($num);
echo $pos;
echo ("\n")
// This code is contributed
// by Shivi_Aggarwal
?>
Javascript
<script>
// Javascript implementation of above approach
let INT_SIZE = 32;
function Right_most_setbit(num)
{
let pos = 1;
// Counting the position of first set bit
for(let i = 0; i < INT_SIZE; i++)
{
if ((num & (1 << i)) == 0)
pos++;
else
break;
}
return pos;
}
// Driver code
let num = 18;
let pos = Right_most_setbit(num);
document.write(pos);
// This code is contributed by mukesh07
</script>
Producción :
2
Complejidad temporal: O(log 2 n)
Espacio auxiliar: O(1)
Otro método usando Shift derecho (>>) :
Inicializar pos=1. Iterar hasta el número> 0, en cada paso verificar si el último bit está configurado. Si se establece el último bit, regresa a la posición actual; de lo contrario, incrementa pos en 1 y desplaza n a la derecha en 1.
C++
// C++ program for above approach
#include<bits/stdc++.h>
using namespace std;
// Program to find position of
// rightmost set bit
int PositionRightmostSetbit(int n)
{
int p=1;
// Iterate till number>0
while(n > 0)
{
// Checking if last bit is set
if(n&1){
return p;
}
// Increment position and right shift number
p++;
n=n>>1;
}
// set bit not found.
return -1;
}
// Driver Code
int main()
{
int n=18;
// Function call
int pos=PositionRightmostSetbit(n);
if(pos!=-1)
cout<<pos;
else
cout<<0;
return 0;
}
// This code is contributed by zishanahmad786
Java
// Java program for above approach
import java.io.*;
class GFG{
// Function to find position of
// rightmost set bit
public static int Last_set_bit(int n)
{
int p = 1;
// Iterate till number>0
while (n > 0)
{
// Checking if last bit is set
if ((n & 1) > 0)
{
return p;
}
// Increment position and
// right shift number
p++;
n = n >> 1;
}
// set bit not found.
return -1;
}
// Driver Code
public static void main(String[] args)
{
int n = 18;
// Function call
int pos = Last_set_bit(n);
if (pos != -1)
System.out.println(pos);
else
System.out.println("0");
}
}
// This code is contributed by RohitOberoi
Python3
# Python program for above approach # Program to find position of # rightmost set bit def PositionRightmostSetbit( n): p = 1 # Iterate till number>0 while(n > 0): # Checking if last bit is set if(n&1): return p # Increment position and right shift number p += 1 n = n>>1 # set bit not found. return -1; # Driver Code n = 18 # Function call pos = PositionRightmostSetbit(n) if(pos != -1): print(pos) else: print(0) # This code is contributed by rohitsingh07052.
C#
// C# program for above approach
using System;
class GFG{
// Function to find position of
// rightmost set bit
public static int Last_set_bit(int n)
{
int p = 1;
// Iterate till number>0
while (n > 0)
{
// Checking if last bit is set
if ((n & 1) > 0)
{
return p;
}
// Increment position and
// right shift number
p++;
n = n >> 1;
}
// Set bit not found.
return -1;
}
// Driver Code
public static void Main(string[] args)
{
int n = 18;
// Function call
int pos = Last_set_bit(n);
if (pos != -1)
Console.WriteLine(pos);
else
Console.WriteLine("0");
}
}
// This code is contributed by AnkThon
Javascript
<script>
// Javascript program for above approach
// Program to find position of
// rightmost set bit
function Last_set_bit(n)
{
let p = 1;
// Iterate till number>0
while (n > 0)
{
// Checking if last bit is set
if ((n & 1) > 0)
{
return p;
}
// Increment position and
// right shift number
p++;
n = n >> 1;
}
// Set bit not found.
return -1;
}
// Driver code
let n = 18;
// Function call
let pos = Last_set_bit(n);
if (pos != -1)
{
document.write(pos);
}
else
{
document.write(0);
}
// This code is contributed by divyeshrabadiya07
</script>
Producción
2
Complejidad temporal: O(log 2 n)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA