La complejidad del espacio es el activo más subestimado por los programadores. Apenas se puede ver un límite de memoria excedido (MLE) al enviar una solución. Pero ahorrar memoria es lo más importante que debe cuidar un programador. Si uno necesita crear una aplicación para un usuario, debe hacerse tan eficiente en memoria como sea posible. Las arrays
booleanas se han utilizado como contenedor para resolver diferentes problemas. Este artículo se centra en discutir las alternativas a las arrays booleanas.
Variable entera como contenedor
En general, la variable Integer tiene 4 bytes (se tiene en cuenta C++), lo que da como resultado 32 bits booleanos para representar un número. Por ejemplo, para representar 10, los bits booleanos se pueden escribir como:
int a = 10
En memoria
: 00000000000000000000000000001010 (Binario de 10 en entero de 32 bits)
Esto significa que uno puede usar estos bits como un valor booleano dentro de una array booleana de tamaño 32. Se puede usar un número entero de 64 bits para aumentar el tamaño si es necesario.
¿Cómo usar la variable Integer como contenedor?
Analicemos en detalle cómo usar la variable Integer como contenedor.
El primer paso es inicializar la variable entera como 0, para obtener el contenedor booleano de tamaño 32 con todos los bits inicialmente falsos.
Establecer un bit en verdadero:
establezca cualquier bit en verdadero para cualquier ubicación deseada mediante el uso de operadores bit a bit como operadores AND, NOT, OR y SHIFT . Por ejemplo, para establecer un bit en verdadero en la posición 7-
Use shift y el operador OR bit a bit para hacer que el i -ésimo bit sea 1 (verdadero)
int a = 0;
a |= (1 << 7);
Aquí a se convertirá en: 000000000000000000000000010000000
↑
0 th bit
Paso 1: Primero mueva 1 que es (..0001) en binario a 7 pasos restantes para hacerlo como (..10000000).
Paso 2: A continuación, hazlo bit a bit o con el número.
Paso 3: Como 1 O 0 = 1 y 1 O 1 = 1, esto establecerá el bit 7 a uno sin afectar a otros bits.
Establezca un bit en falso:
Por ejemplo, para restablecer un bit a falso en la posición 7
Utilice shift y el operador NOT y AND bit a bit para hacer que el i -ésimo bit sea 0 (falso).
int a = 0;
a |= (1 << 7); // Para establecer el séptimo bit
a &= ~(1 << 7); // Para restablecer el bit 7
Paso 1: Primero mueva nuestro 1 que es (..0001) en binario a 7 pasos a la izquierda para convertirlo en (..10000000).
Paso 2: invierta los bits para que se vean como (… 1101111111).
Paso 3: Realice la operación AND con el número.
Paso 4: Como 1 Y 0 = 0, 0 Y 0 = 0, 1 Y 1 = 1, esto establecerá el bit 7 a uno sin afectar a otros bits.
Obtener el valor de i th bit:
Por ejemplo, para obtener el valor del 7º bit-
Utilice el operador AND para imprimir.
int a = 0;
a |= (1<<7); // Para configurar el 7mo bit
Print((a>>7)&1); // esto imprimirá 1(Verdadero)
a &= ~(1<<7); // Para restablecer el 7mo bit
Print((a>>7)&1); // esto imprimirá 0 (falso)
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include<iostream>
using namespace std;
// Driver code
int main()
{
// This is an integer variable
// used as a container
int myBoolContainer = 0;
// 7th bit will be used for sample
int workingBit = 7;
// Setting ith bit
cout << "Setting " <<
workingBit << "th bit to 1\n";
myBoolContainer |= (1 << workingBit);
// Printing the ith bit
cout << "Value at " << workingBit <<
"th bit = " <<
((myBoolContainer >> workingBit) & 1) <<
"\n\n";
// Resetting the ith bit
cout << "Resetting " << workingBit <<
"th bit to 0\n";
myBoolContainer &= ~(1 << 7);
// Printing the ith bit
cout << "Value at " << workingBit <<
"th bit = " <<
((myBoolContainer >> workingBit) & 1);
}
Java
// Java program to implement
// the above approach
import java.io.*;
// Driver code
class GFG
{
public static void main (String[] args)
{
// This will be the integer variable
// used as boolean container
int myBoolContainer = 0;
// 7th bit will be used for sample
int workingBit = 7;
// Setting ith bit
System.out.println(
"Setting " + workingBit +
"th bit to 1");
myBoolContainer |= (1 << workingBit);
// Printing the ith bit
System.out.println(
"Value at " + workingBit+"th bit = " +
((myBoolContainer >> workingBit) & 1) +
"\n");
// Resetting the ith bit
System.out.println(
"Resetting " + workingBit +
"th bit to 0");
myBoolContainer &= ~(1 << 7);
// Printing the ith bit
System.out.println(
"Value at " + workingBit +
"th bit = " +
((myBoolContainer >>workingBit) & 1));
}
}
Python
# Python program to implement
# the above approach
# This will be the integer variable
# used as boolean container
myBoolContainer = 0;
# 7th bit will be used as example
workingBit = 7;
# Setting ith bit
print("Setting " + str(workingBit) +
"th bit to 1");
myBoolContainer |= (1 << workingBit);
# Printing the ith bit
print("Value at " + str(workingBit) +
"th bit = " + str((myBoolContainer >>
workingBit) & 1) + "\n");
# Resetting the ith bit
print("Resetting " + str(workingBit) +
"th bit to 0");
myBoolContainer &= ~(1 << 7);
# Printing the ith bit
print("Value at " + str(workingBit) +
"th bit = " + str((myBoolContainer >>
workingBit) & 1))
C#
//C# code for the above approach
using System;
public class GFG {
static public void Main()
{
// This will be the integer variable
// used as boolean container
int myBoolContainer = 0;
// 7th bit will be used for sample
int workingBit = 7;
// Setting ith bit
Console.WriteLine("Setting " + workingBit
+ "th bit to 1");
myBoolContainer |= (1 << workingBit);
// Printing the ith bit
Console.WriteLine(
"Value at " + workingBit + "th bit = "
+ ((myBoolContainer >> workingBit) & 1) + "\n");
// Resetting the ith bit
Console.WriteLine("Resetting " + workingBit
+ "th bit to 0");
myBoolContainer &= ~(1 << 7);
// Printing the ith bit
Console.WriteLine(
"Value at " + workingBit + "th bit = "
+ ((myBoolContainer >> workingBit) & 1));
}
}
// This code is contributed by Potta Lokesh
Javascript
// Javascript program to implement
// the above approach
// This is an integer variable
// used as a container
var myBoolContainer = 0;
// 7th bit will be used sample
var workingBit = 7;
// Setting ith bit
console.log("Setting " + workingBit +
"th bit to 1\n");
myBoolContainer |= (1 << workingBit);
//Printing the ith bit
console.log("Value at " + workingBit +
"th bit = "+ ((myBoolContainer >>
workingBit) & 1) + "\n\n");
// Resetting the ith bit
console.log("Resetting " + workingBit +
"th bit to 0\n");
myBoolContainer &= ~(1 << 7);
// Printing the ith bit
console.log("Value at " + workingBit +
"th bit = " + ((myBoolContainer >>
workingBit) & 1));
Setting 7th bit to 1 Value at 7th bit = 1 Resetting 7th bit to 0 Value at 7th bit = 0
Resolver strings de pangrama:
Resolvamos el problema de las strings de pangrama usando el enfoque anterior.
Acercarse:
Se sabe que los alfabetos ingleses del rango de minúsculas desde (az) tienen un conteo de no más de 26. Entonces, en este enfoque, se puede usar una array bool de tamaño constante. Esto optimizará la complejidad espacial del código.
A continuación se muestra la implementación de las strings de pangrama utilizando una array booleana:
C++
// C++ program to implement
// the above approach
#include <iostream>
using namespace std;
bool checkIsPanagram(string sentence)
{
// Initializing the container
int n = 0;
for(char &x:sentence)
{
// Checking that the char
// is Alphabetic
if(isalpha(x))
// setting ith bit to 1
// if char is 'a' then this will
// set 0th bit to 1 and so on
n |= (1 << (tolower(x) - 'a'));
}
// decimal number for all ones in last
// 26 bits in binary is 67108863
return n == 67108863;
}
// Driver code
int main()
{
string s =
"Pack mY box witH fIve dozen liquor jugs";
cout << checkIsPanagram(s);
}
Java
// Java program to implement
// the above approach
import java.io.*;
class Panagram
{
public boolean checkIsPanagram(
String sentence)
{
// Initializing the container
int n = 0;
int size = sentence.length();
for(int i = 0; i < size; i++)
{
// Storing current character
// in temp variable
char x = sentence.charAt(i);
// checking that the char is Alphabetic
if(Character.isAlphabetic(x))
{
// setting ith bit to 1
// if char is 'a' then this will
// set 0th bit to 1 and so on
n |= (1 << (Character.toLowerCase(x) - 'a'));
}
}
// Decimal number for all ones in last
// 26 bits in binary is 67108863
return (n == 67108863);
}
};
// Driver code
class GFG
{
public static void main (String[] args)
{
String s =
"Pack mY box witH fIve dozen liquor jugs";
Panagram panagram = new Panagram();
System.out.println(
panagram.checkIsPanagram(s));
}
}
Python
# Python program to implement
# the above approach
def isPanagram(sentence):
# Initializing the container
n = 0
for char in sentence:
# Checking that the char
# is Alphabetic
if char.isalpha():
# setting ith bit to 1
# if char is a then this will
# set 0th bit to 1 and so on
n |= (1 << (ord(char.lower()) -
ord('a')))
# Decimal number for all ones in
# last 26 bits in binary is 67108863
return n == 67108863
sentence =
"Pack mY box witH fIve dozen liquor jugs"
print(isPanagram(sentence))
C#
// C# program to implement
// the above approach
using System;
class Panagram
{
public bool checkIsPanagram(
String sentence)
{
// Initializing the container
int n = 0;
int size = sentence.Length;
for(int i = 0; i < size; i++)
{
// Storing current character
// in temp variable
char x = sentence[i];
// checking that the char is Alphabetic
if(char.IsLetter(x))
{
// setting ith bit to 1
// if char is 'a' then this will
// set 0th bit to 1 and so on
n |= (1 << (char.ToLower(x) - 'a'));
}
}
// Decimal number for all ones in last
// 26 bits in binary is 67108863
return (n == 67108863);
}
};
// Driver code
public class GFG
{
public static void Main(String[] args)
{
String s =
"Pack mY box witH fIve dozen liquor jugs";
Panagram panagram = new Panagram();
Console.WriteLine(
panagram.checkIsPanagram(s));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// javascript program to implement
// the above approach
function checkIsPanagram(sentence)
{
// Initializing the container
var n = 0;
var size = sentence.length;
for(var i = 0; i < size; i++)
{
// Storing current character
// in temp variable
var x = sentence[i];
// checking that the char is Alphabetic
if(isAlphabetic(x))
{
// setting ith bit to 1
// if char is 'a' then this will
// set 0th bit to 1 and so on
n = n | (1 << (x.charCodeAt(0)- 'a'.charCodeAt(0)));
}
}
// Decimal number for all ones in last
// 26 bits in binary is 67108863
return (n == 67108863);
}
function isAlphabetic(str)
{
return /^[a-zA-Z()]+$/.test(str);
}
// Driver code
var s =
"Pack mY box witH fIve dozen liquor jugs";
document.write(checkIsPanagram(s));
// This code is contributed by 29AjayKumar
</script>
1
Publicación traducida automáticamente
Artículo escrito por kaustubhvats08 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA