Dado un entero positivo N , la tarea es encontrar el número que se puede obtener cambiando bits de conjunto consecutivos comenzando desde el LSB en la representación binaria de N .
Ejemplos:
Entrada: N = 39
Salida: 32
Explicación:
Representación binaria de (39) 10 = (100111) 2
Después de voltear todos los bits consecutivos comenzando desde el LSB, el número obtenido es (100000)
La representación binaria de (32) 10 es (100000 ) 2
Por lo tanto, el número obtenido es 32.Entrada: N = 4
Salida: 4
Explicación:
Representación binaria de (4) 10 = (100) 2
Dado que el LSB no está configurado, el número permanece sin cambios.
Enfoque ingenuo: el enfoque más simple es encontrar el número de bits establecidos consecutivos a partir del LSB realizando AND lógico ( & ) de N con 1 hasta que N & 1 no sea 0 y mantener una cuenta del número de bits establecidos . Luego, simplemente desplace N a la izquierda por el conteo de bits establecidos . Escriba el número obtenido como respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the number after
// converting 1s from end to 0s
int findNumber(int N)
{
// Count of 1s
int count = 0;
// AND operation of N and 1
while ((N & 1) == 1) {
N = N >> 1;
count++;
}
// Left shift N by count
return N << count;
}
// Driver Code
int main()
{
int N = 39;
// Function Call
cout << findNumber(N);
return 0;
}
Java
// Java program for the above approach
class GFG{
// Function to find the number after
// converting 1s from end to 0s
static int findNumber(int N)
{
// Count of 1s
int count = 0;
// AND operation of N and 1
while ((N & 1) == 1)
{
N = N >> 1;
count++;
}
// Left shift N by count
return N << count;
}
// Driver Code
public static void main (String[] args)
{
int N = 39;
// Function Call
System.out.println(findNumber(N));
}
}
// This code is contributed by AnkThon
Python3
# Python3 program for the above approach # Function to find the number after # converting 1s from end to 0s def findNumber(N): # Count of 1s count = 0 # AND operation of N and 1 while ((N & 1) == 1): N = N >> 1 count += 1 # Left shift N by count return N << count # Driver Code if __name__ == "__main__": N = 39 # Function Call print(findNumber(N)) # This code is contributed by AnkThon
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to find the number after
// converting 1s from end to 0s
static int findNumber(int N)
{
// Count of 1s
int count = 0;
// AND operation of N and 1
while ((N & 1) == 1)
{
N = N >> 1;
count++;
}
// Left shift N by count
return N << count;
}
// Driver Code
public static void Main()
{
int N = 39;
// Function Call
Console.WriteLine(findNumber(N));
}
}
// This code is contributed by code_hunt
Javascript
<script>
// Javascript program for the above approach
// Function to find the number after
// converting 1s from end to 0s
function findNumber(N)
{
// Count of 1s
let count = 0;
// AND operation of N and 1
while ((N & 1) == 1)
{
N = N >> 1;
count++;
}
// Left shift N by count
return N << count;
}
// Driver Code
let N = 39;
// Function Call
document.write(findNumber(N));
</script>
32
Complejidad temporal: O(log N)
Espacio auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, encuentre el AND lógico ( & ) de N y (N + 1) . La observación clave es que agregar 1 a un número hace que cada bit establecido continuo desde el LSB se convierta en 0 . Por lo tanto, N & (N + 1) da el número requerido.
Ilustración:
N = 39, therefore (N+1)=40 ⇒ N = 39 = (100111) ⇒ N+1 = 40 = (101000) Performing Logical AND(&) operation: 1 0 0 1 1 1 & 1 0 1 0 0 0 ---------------- 1 0 0 0 0 0 ⇒ 32 ---------------- Will this always work? Add 1 to N: 1 0 0 1 1 1 + 1 ------------- 1 0 1 0 0 0 -------------- It can be clearly seen that the continuous set bits from the LSB becomes unset.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the number after
// converting 1s from end to 0s
int findNumber(int N)
{
// Return the logical AND
// of N and (N + 1)
return N & (N + 1);
}
// Driver Code
int main()
{
int N = 39;
// Function Call
cout << findNumber(N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the number after
// converting 1s from end to 0s
static int findNumber(int N)
{
// Return the logical AND
// of N and (N + 1)
return N & (N + 1);
}
// Driver Code
public static void main(String[] args)
{
int N = 39;
// Function Call
System.out.print(findNumber(N));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program for the above approach # Function to find the number after # converting 1s from end to 0s def findNumber(N): # Return the logical AND # of N and (N + 1) return N & (N + 1) # Driver Code if __name__ == '__main__': N = 39 # Function Call print(findNumber(N)) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
class GFG
{
// Function to find the number after
// converting 1s from end to 0s
static int findNumber(int N)
{
// Return the logical AND
// of N and (N + 1)
return N & (N + 1);
}
// Driver Code
public static void Main(String[] args)
{
int N = 39;
// Function Call
Console.Write(findNumber(N));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// javascript program of the above approach
// Function to find the number after
// converting 1s from end to 0s
function findNumber(N)
{
// Return the logical AND
// of N and (N + 1)
return N & (N + 1);
}
// Driver Code
let N = 39;
// Function Call
document.write(findNumber(N));
// This code is contributed by target_2.
</script>
32
Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por rathoreatul27 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA