La manipulación de bits es una técnica utilizada en una variedad de problemas para obtener la solución de manera optimizada. Esta técnica es muy efectiva desde el punto de vista de la Programación Competitiva . Se trata de operadores bit a bit que funcionan directamente sobre números binarios o bits de números que ayudan a la implementación rápida. A continuación se muestran los operadores bit a bit que se utilizan:
- Bit a bit Y (&)
- Bit a bit O (|)
- XOR bit a bit (^)
- Bit a bit NO (!)
Obtenga más información sobre los operadores bit a bit en este artículo .
A continuación se muestran algunas operaciones de bits comunes que se utilizan con frecuencia en la programación:
Operaciones bit a bit :
A continuación se muestra la tabla para ilustrar el resultado cuando la operación se realiza utilizando operadores bit a bit. Aquí 0 o 1 significan una secuencia de 0 o 1 respectivamente.
| Operadores | Operaciones | Resultado |
|---|---|---|
| XOR | X ^ 0s | X |
| XOR | X ^ 1s | ~ X |
| XOR | X ^ X | 0 |
| Y | X y 0 | 0 |
| Y | X y 1 | X |
| Y | X y X | X |
| O | X | 0s | X |
| O | X | 1s | 1s |
| O | X | X | X |
Obtener un poco :
Este método se usa para encontrar el bit en una posición particular (por ejemplo, i ) del número dado N. La idea es encontrar el AND bit a bit del número dado y 2 i que se pueden representar como (1 << i) . Si el valor devuelto es 1 , entonces se establece el bit en la i -ésima posición . De lo contrario, está desarmado.
A continuación se muestra el pseudocódigo para el mismo:
C++
// Function to get the bit at the
// ith position
boolean getBit(int num, int i)
{
// Return true if the bit is
// set. Otherwise return false
return ((num & (1 << i)) != 0);
}
Java
// Function to get the bit at the
// ith position
static boolean getBit(int num, int i)
{
// Return true if the bit is
// set. Otherwise return false
return ((num & (1 << i)) != 0);
}
// This code is contributed by rishavmahato348.
Python3
# Function to get the bit at the # ith position def getBit(num, i): # Return true if the bit is # set. Otherwise return false return ((num & (1 << i)) != 0) # This code is contributed by shivani
C#
// Function to get the bit at the
// ith position
static bool getBit(int num, int i)
{
// Return true if the bit is
// set. Otherwise return false
return ((num & (1 << i)) != 0);
}
// This code is contributed by subhammahato348.
Javascript
<script>
// Function to get the bit at the
// ith position
function getBit(num, i)
{
// Return true if the bit is
// set. Otherwise return false
return ((num & (1 << i)) != 0);
}
// This code is contributed by Ankita saini
</script>
Establecer bits :
Este método se usa para establecer el bit en una posición particular (por ejemplo, i ) del número dado N. La idea es actualizar el valor del número dado N al OR bit a bit del número dado N y 2 i que se puede representar como (1 << i) . Si el valor devuelto es 1 , entonces se establece el bit en la i -ésima posición . De lo contrario, está desarmado.
A continuación se muestra el pseudocódigo para el mismo:
C++
// Function to set the ith bit of the
// given number num
int setBit(int num, int i)
{
// Sets the ith bit and return
// the updated value
return num | (1 << i);
}
Java
// Function to set the ith bit of the
// given number num
static int setBit(int num, int i)
{
// Sets the ith bit and return
// the updated value
return num | (1 << i);
}
// This code is contributed by subhammahato348
Python3
# Function to set the ith bit of the # given number num def setBit(num, i): # Sets the ith bit and return # the updated value return num | (1 << i) # This code is contributed by kirti
C#
// Function to set the ith bit of the
// given number num
static int setBit(int num, int i)
{
// Sets the ith bit and return
// the updated value
return num | (1 << i);
}
Javascript
// Function to set the ith bit of the
// given number num
function setBit(num, i)
{
// Sets the ith bit and return
// the updated value
return num | (1 << i);
}
Borrar bit :
Este método se usa para borrar el bit en una posición particular (por ejemplo, i ) del número dado N. La idea es actualizar el valor del número dado N al AND bit a bit del número dado N y el complemento de 2 i que se puede representar como ~(1 << i) . Si el valor devuelto es 1 , entonces se establece el bit en la i -ésima posición . De lo contrario, está desarmado.
A continuación se muestra el pseudocódigo para el mismo:
C++
// Function to clear the ith bit of
// the given number N
int clearBit(int num, int i)
{
// Create the mask for the ith
// bit unset
int mask = ~(1 << i);
// Return the update value
return num & mask;
}
Java
// Function to clear the ith bit of
// the given number N
static int clearBit(int num, int i)
{
// Create the mask for the ith
// bit unset
int mask = ~(1 << i);
// Return the update value
return num & mask;
}
// This code is contributed by subham348
Python3
# Function to clear the ith bit of # the given number N def clearBit(num, i): # Create the mask for the ith # bit unset mask = ~(1 << i) # Return the update value return num & mask # This code is contributed by subhammahato348
C#
// Function to clear the ith bit of
// the given number N
static int clearBit(int num, int i)
{
// Create the mask for the ith
// bit unset
int mask = ~(1 << i);
// Return the update value
return num & mask;
}
// This code is contributed by Ankita Saini
Javascript
// Function to clear the ith bit of
// the given number N
function clearBit(num, i)
{
// Create the mask for the ith
// bit unset
let mask = ~(1 << i);
// Return the update value
return num & mask;
}
// This code is contributed by souravmahato348.
A continuación se muestra el programa que implementa las funcionalidades anteriores:
C++
// C++ program to implement all the
// above functionalities
#include "bits/stdc++.h"
using namespace std;
// Function to get the bit at the
// ith position
bool getBit(int num, int i)
{
// Return true if the ith bit is
// set. Otherwise return false
return ((num & (1 << i)) != 0);
}
// Function to set the ith bit of the
// given number num
int setBit(int num, int i)
{
// Sets the ith bit and return
// the updated value
return num | (1 << i);
}
// Function to clear the ith bit of
// the given number N
int clearBit(int num, int i)
{
// Create the mask for the ith
// bit unset
int mask = ~(1 << i);
// Return the update value
return num & mask;
}
// Driver Code
int main()
{
// Given number N
int N = 70;
cout << "The bit at the 3rd position from LSB is: "
<< (getBit(N, 3) ? '1' : '0')
<< endl;
cout << "The value of the given number "
<< "after setting the bit at "
<< "LSB is: "
<< setBit(N, 0) << endl;
cout << "The value of the given number "
<< "after clearing the bit at "
<< "LSB is: "
<< clearBit(N, 0) << endl;
return 0;
}
Java
// Java program to implement all the
// above functionalities
import java.io.*;
class GFG{
// Function to get the bit at the
// ith position
static boolean getBit(int num, int i)
{
// Return true if the ith bit is
// set. Otherwise return false
return ((num & (1 << i)) != 0);
}
// Function to set the ith bit of the
// given number num
static int setBit(int num, int i)
{
// Sets the ith bit and return
// the updated value
return num | (1 << i);
}
// Function to clear the ith bit of
// the given number N
static int clearBit(int num, int i)
{
// Create the mask for the ith
// bit unset
int mask = ~(1 << i);
// Return the update value
return num & mask;
}
// Driver Code
public static void main(String[] args)
{
// Given number N
int N = 70;
System.out.println("The bit at the 3rd position from LSB is: " +
(getBit(N, 3) ? '1' : '0'));
System.out.println("The value of the given number " +
"after setting the bit at " +
"LSB is: " + setBit(N, 0));
System.out.println("The value of the given number " +
"after clearing the bit at " +
"LSB is: " + clearBit(N, 0));
}
}
// This code is contributed by souravmahato348
Python
# Python program to implement all the # above functionalities # Function to get the bit at the # ith position def getBit( num, i): # Return true if the ith bit is # set. Otherwise return false return ((num & (1 << i)) != 0) # Function to set the ith bit of the # given number num def setBit( num, i): # Sets the ith bit and return # the updated value return num | (1 << i) # Function to clear the ith bit of # the given number N def clearBit( num, i): # Create the mask for the ith # bit unset mask = ~(1 << i) # Return the update value return num & mask # Driver Code # Given number N N = 70 print"The bit at the 3rd position from LSB is: " , 1 if (getBit(N, 3)) else '0' print"The value of the given number" , "after setting the bit at","LSB is: " , setBit(N, 0) print"The value of the given number" , "after clearing the bit at","LSB is: " , clearBit(N, 0) # This code is contributed by shivanisinghss2110
C#
// C# program to implement all the
// above functionalities
using System;
class GFG {
// Function to get the bit at the
// ith position
static bool getBit(int num, int i)
{
// Return true if the ith bit is
// set. Otherwise return false
return ((num & (1 << i)) != 0);
}
// Function to set the ith bit of the
// given number num
static int setBit(int num, int i)
{
// Sets the ith bit and return
// the updated value
return num | (1 << i);
}
// Function to clear the ith bit of
// the given number N
static int clearBit(int num, int i)
{
// Create the mask for the ith
// bit unset
int mask = ~(1 << i);
// Return the update value
return num & mask;
}
// Driver Code
public static void Main()
{
// Given number N
int N = 70;
Console.WriteLine("The bit at the 3rd position form LSB is: "
+ (getBit(N, 3) ? '1' : '0'));
Console.WriteLine("The value of the given number "
+ "after setting the bit at "
+ "LSB is: " + setBit(N, 0));
Console.WriteLine("The value of the given number "
+ "after clearing the bit at "
+ "LSB is: " + clearBit(N, 0));
}
}
// This code is contributed by rishavmahato348.
Javascript
<script>
// Javascript program to implement all
// the above functionalities
// Function to get the bit at the
// ith position
function getBit(num, i)
{
// Return true if the ith bit is
// set. Otherwise return false
return ((num & (1 << i)) != 0);
}
// Function to set the ith bit of the
// given number num
function setBit(num, i)
{
// Sets the ith bit and return
// the updated value
return num | (1 << i);
}
// Function to clear the ith bit of
// the given number N
function clearBit(num, i)
{
// Create the mask for the ith
// bit unset
let mask = ~(1 << i);
// Return the update value
return num & mask;
}
// Driver code
// Given number N
let N = 70;
document.write("The bit at the 3rd position from LSB is: " +
(getBit(N, 3) ? '1' : '0') + "</br>");
document.write("The value of the given number " +
"after setting the bit at " +
"LSB is: " + setBit(N, 0) + "</br>");
document.write("The value of the given number " +
"after clearing the bit at " +
"LSB is: " + clearBit(N, 0) + "</br>");
// This code is contributed by divyeshrabadiya07
</script>
Producción:
The bit at the 3rd position is: 0 The value of the given number after setting the bit at MSB is: 71 The value of the given number after clearing the bit at MSB is: 70