Dado un número entero N , la tarea es voltear todos los bits a la izquierda del bit establecido más a la derecha e imprimir el número generado.
Ejemplos:
Entrada: N = 10
Salida: 6
Explicación:
10 (1010 en binario)
volteando todos los bits de izquierda a derecha set bit (índice 2)
-> 6 (0110 en binario)Entrada: N = 120
Salida: 8
Explicación:
120 (1111000 en binario)
volteando todos los bits de izquierda a derecha establece el bit (índice 3)
-> 8 (0001000 en binario)
Enfoque ingenuo:
para resolver el problema mencionado anteriormente, seguiremos los pasos que se detallan a continuación:
- Convierta el entero dado en su forma binaria y almacene cada bit en una array.
- Atraviese la array y rompa después de la primera aparición de 1.
- Voltea todos los bits a la izquierda de ese índice. Convierte esa secuencia binaria en un número decimal y devuélvelo.
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Enfoque eficiente:
para optimizar el método anterior, intentaremos utilizar operadores bit a bit .
- Estamos encontrando la posición del bit establecido desde el lado más a la derecha que es LSB y el número total de bits.
- XOR el número dado con el número que tiene todos los bits establecidos que tienen un total de bits establecidos igual al número total de bits.
- No queremos voltear los bits más a la derecha de un bit establecido. Entonces, nuevamente estamos tomando XOR con el número que tiene todos los bits establecidos que tienen un total de bits establecidos igual al primer bit
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the
// integer formed after flipping
// all bits to the left of the
// rightmost set bit
#include <bits/stdc++.h>
using namespace std;
int totCount;
int firstCount;
// Function to get the total count
void getTotCount(int num)
{
totCount = 1;
firstCount = 1;
int temp = 1;
// Moving until we get
// the rightmost set bit
while ((num & temp) == 0)
{
temp = temp << 1;
totCount += 1;
}
firstCount = totCount;
temp = num >> totCount;
// To get total number
// of bits in a number
while (temp != 0)
{
totCount += 1;
temp = temp >> 1;
}
}
// Function to find the integer formed
// after flipping all bits to the left
// of the rightmost set bit
int flipBitsFromRightMostSetBit(int num)
{
// Find the total count of bits and
// the rightmost set bit
getTotCount(num);
// XOR given number with the
// number which has is made up
// of only totbits set
int num1 = num ^ ((1 << totCount) - 1);
// To avoid flipping the bits
// to the right of the set bit,
// take XOR with the number
// made up of only set firstbits
num1 = num1 ^ ((1 << firstCount) - 1);
return num1;
}
// Driver Code
int main()
{
int n = 120;
cout << flipBitsFromRightMostSetBit(n)
<< endl;
return 0;
}
// This code is contributed by divyeshrabadiya07
Java
// Java program to find the
// integer formed after flipping
// all bits to the left of the
// rightmost set bit
import java.util.*;
class GFG{
static int totCount;
static int firstCount;
// Function to get the total count
static void getTotCount(int num)
{
totCount = 1;
firstCount = 1;
int temp = 1;
// Moving until we get
// the rightmost set bit
while ((num & temp) == 0)
{
temp = temp << 1;
totCount += 1;
}
firstCount = totCount;
temp = num >> totCount;
// To get total number
// of bits in a number
while (temp != 0)
{
totCount += 1;
temp = temp >> 1;
}
}
// Function to find the integer formed
// after flipping all bits to the left
// of the rightmost set bit
static int flipBitsFromRightMostSetBit(int num)
{
// Find the total count of bits and
// the rightmost set bit
getTotCount(num);
// XOR given number with the
// number which has is made up
// of only totbits set
int num1 = num ^ ((1 << totCount) - 1);
// To avoid flipping the bits
// to the right of the set bit,
// take XOR with the number
// made up of only set firstbits
num1 = num1 ^ ((1 << firstCount) - 1);
return num1;
}
// Driver Code
public static void main (String[] args)
{
int n = 120;
System.out.println(
flipBitsFromRightMostSetBit(n));
}
}
// This code is contributed by offbeat
Python3
# Python3 program to find the # integer formed after flipping # all bits to the left of the # rightmost set bit # Function to get the total count def getTotCount(num): totCount = 1 firstCount = 1 temp = 1 # Moving until we get # the rightmost set bit while (not(num & temp)): temp = temp << 1 totCount += 1 firstCount = totCount temp = num >> totCount # To get total number # of bits in a number while (temp): totCount += 1 temp = temp >> 1 return totCount, firstCount # Function to find the integer formed # after flipping all bits to the left # of the rightmost set bit def flipBitsFromRightMostSetBit(num): # Find the total count of bits and # the rightmost set bit totbit, firstbit = getTotCount(num) # XOR given number with the # number which has is made up # of only totbits set num1 = num ^ ((1 << totbit) - 1) # To avoid flipping the bits # to the right of the set bit, # take XOR with the number # made up of only set firstbits num1 = num1 ^ ((1 << firstbit) - 1) return num1 if __name__=='__main__': n = 120 print(flipBitsFromRightMostSetBit(n))
C#
// C# program to find the
// integer formed after flipping
// all bits to the left of the
// rightmost set bit
using System;
class GFG{
static int totCount;
static int firstCount;
// Function to get the total count
static void getTotCount(int num)
{
totCount = 1;
firstCount = 1;
int temp = 1;
// Moving until we get
// the rightmost set bit
while ((num & temp) == 0)
{
temp = temp << 1;
totCount += 1;
}
firstCount = totCount;
temp = num >> totCount;
// To get total number
// of bits in a number
while (temp != 0)
{
totCount += 1;
temp = temp >> 1;
}
}
// Function to find the integer formed
// after flipping all bits to the left
// of the rightmost set bit
static int flipBitsFromRightMostSetBit(int num)
{
// Find the total count of bits and
// the rightmost set bit
getTotCount(num);
// XOR given number with the
// number which has is made up
// of only totbits set
int num1 = num ^ ((1 << totCount) - 1);
// To avoid flipping the bits
// to the right of the set bit,
// take XOR with the number
// made up of only set firstbits
num1 = num1 ^ ((1 << firstCount) - 1);
return num1;
}
// Driver Code
public static void Main (string[] args)
{
int n = 120;
Console.Write(
flipBitsFromRightMostSetBit(n));
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// JavaScript program to find the
// integer formed after flipping
// all bits to the left of the
// rightmost set bit
let totCount;
let firstCount;
// Function to get the total count
function getTotCount(num)
{
totCount = 1;
firstCount = 1;
let temp = 1;
// Moving until we get
// the rightmost set bit
while ((num & temp) == 0)
{
temp = temp << 1;
totCount += 1;
}
firstCount = totCount;
temp = num >> totCount;
// To get total number
// of bits in a number
while (temp != 0)
{
totCount += 1;
temp = temp >> 1;
}
}
// Function to find the integer formed
// after flipping all bits to the left
// of the rightmost set bit
function flipBitsFromRightMostSetBit(num)
{
// Find the total count of bits and
// the rightmost set bit
getTotCount(num);
// XOR given number with the
// number which has is made up
// of only totbits set
let num1 = num ^ ((1 << totCount) - 1);
// To avoid flipping the bits
// to the right of the set bit,
// take XOR with the number
// made up of only set firstbits
num1 = num1 ^ ((1 << firstCount) - 1);
return num1;
}
// Driver Code
let n = 120;
document.write(flipBitsFromRightMostSetBit(n));
// This code is contributed by sanjoy_62
</script>
Producción:
8
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por shubhamjagdhane y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA