Dada una array arr[] de strings binarias, la tarea es calcular el AND bit a bit de todas estas strings e imprimir la string resultante.
Ejemplos:
Input: arr[] = {"101", "110110", "111"}
Output: 000100
(000101) & (110110) & (000111) = 000100
Input: arr[] = {"110010101", "111101001"}
Output: 110000001
Enfoque 1: similar a Agregar strings de dos bits (https://www.geeksforgeeks.org/add-two-bit-strings/)
Dada una array de N strings binarias. Primero calculamos la operación AND de las dos primeras strings binarias y luego realizamos este «Resultado» con la tercera string binaria y así sucesivamente hasta la última string binaria.
Por ejemplo, string arr[] = {“101”, “110110”, “111”};
Paso 1: Resultado = 101 Y 110110;
Paso 2: Resultado = Resultado (Paso 1) Y 111;
Pronto..
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// Helper method: given two unequal sized
// bit strings, converts them to
// same length by adding leading 0s in the
// smaller string. Returns the new length
int makeEqualLength(string &a, string &b)
{
int len_a = a.length();
int len_b = b.length();
int num_zeros = abs(len_a-len_b);
if (len_a<len_b)
{
for (int i = 0 ; i<num_zeros; i++)
{
a = '0' + a;
}
// Return len_b which is highest.
// No need to proceed further!
return len_b;
}
else
{
for (int i = 0 ; i<num_zeros; i++)
{
b = '0' + b;
}
}
// Return len_a which is greater or
// equal to len_b
return len_a;
}
// The main function that performs AND
// operation of two-bit sequences
// and returns the resultant string
string andOperationBitwise(string s1, string s2)
{
// Make both strings of same length with the
// maximum length of s1 & s2.
int length = makeEqualLength(s1,s2);
// Initialize res as NULL string
string res = "";
// We start from left to right as we have
// made both strings of same length.
for (int i = 0 ; i<length; i++)
{
// Convert s1[i] and s2[i] to int and perform
// bitwise AND operation, append to "res" string
res = res + (char)((s1[i] - '0' & s2[i]-'0')+'0');
}
return res;
}
//Driver Code
int main()
{
string arr[] = {"101", "110110", "111"};
int n = sizeof(arr)/sizeof(arr[0]);
string result;
// Check corner case: If there is just one
// binary string, then print it and return.
if (n<2)
{
cout<<arr[n-1]<<endl;
return 0;
}
result = arr[0];
for (int i = 1; i<n; i++)
{
result = andOperationBitwise(result, arr[i]);
}
cout <<result<<endl;
}
// This code has been contributed by sharathmaidargi
Java
// Java implementation of the above approach
class GFG {
// global fields
static String a;
static String b;
// Helper method: given two unequal sized
// bit strings, converts them to
// same length by adding leading 0s in the
// smaller string. Returns the new length
static int makeEqualLength()
{
int len_a = a.length();
int len_b = b.length();
int num_zeros = Math.abs(len_a - len_b);
if (len_a < len_b) {
for (int i = 0; i < num_zeros; i++) {
a = '0' + a;
}
// Return len_b which is highest.
// No need to proceed further!
return len_b;
}
else {
for (int i = 0; i < num_zeros; i++) {
b = '0' + b;
}
}
// Return len_a which is greater or
// equal to len_b
return len_a;
}
// The main function that performs AND
// operation of two-bit sequences
// and returns the resultant string
static String andOperationBitwise(String s1, String s2)
{
// Make both strings of same length with the
// maximum length of s1 & s2.
a = s1;
b = s2;
int length = makeEqualLength();
s1 = a;
s2 = b;
// Initialize res as NULL string
String res = "";
// We start from left to right as we have
// made both strings of same length.
for (int i = 0; i < length; i++) {
// Convert s1[i] and s2[i] to int and perform
// bitwise AND operation, append to "res" string
res = res
+ (char)((s1.charAt(i) - '0'
& s2.charAt(i) - '0')
+ '0');
}
return res;
}
// Driver code
public static void main(String[] args)
{
String arr[] = { "101", "110110", "111" };
int n = arr.length;
String result = "";
// Check corner case: If there is just one
// binary string, then print it and return.
if (n < 2) {
System.out.println(arr[n - 1]);
}
result = arr[0];
for (int i = 1; i < n; i++) {
result = andOperationBitwise(result, arr[i]);
}
System.out.println(result);
}
}
// This code is contributed by phasing17
Python3
# Python3 implementation of above approach # this function takes two unequal sized # bit strings, converts them to # same length by adding leading 0s in the # smaller string. Returns the new length def makeEqualLength(a, b): len_a = len(a) len_b = len(b) num_zeros = abs(len_a - len_b) if (len_a < len_b): for i in range(num_zeros): a = '0' + a # Return len_b which is highest. # No need to proceed further! return len_b, a, b else: for i in range(num_zeros): b = '0' + b # Return len_a which is greater or # equal to len_b return len_a, a, b # The main function that performs AND # operation of two-bit sequences # and returns the resultant string def andOperationBitwise(s1, s2): # Make both strings of same length # with the maximum length of s1 & s2. length, s1, s2 = makeEqualLength(s1, s2) # Initialize res as NULL string res = "" # We start from left to right as we have # made both strings of same length. for i in range(length): # Convert s1[i] and s2[i] to int # and perform bitwise AND operation, # append to "res" string res = res + str(int(s1[i]) & int(s2[i])) return res # Driver Code arr = ["101", "110110", "111"] n = len(arr) if (n < 2): print(arr[n - 1]) else: result = arr[0] for i in range(n): result = andOperationBitwise(result, arr[i]); print(result) # This code is contributed by # ANKITKUMAR34
C#
// C# implementation of the above approach
using System;
class GFG {
// global fields
static string a;
static string b;
// Helper method: given two unequal sized
// bit strings, converts them to
// same length by adding leading 0s in the
// smaller string. Returns the new length
static int makeEqualLength()
{
int len_a = a.Length;
int len_b = b.Length;
int num_zeros = Math.Abs(len_a - len_b);
if (len_a < len_b) {
for (int i = 0; i < num_zeros; i++) {
a = '0' + a;
}
// Return len_b which is highest.
// No need to proceed further!
return len_b;
}
else {
for (int i = 0; i < num_zeros; i++) {
b = '0' + b;
}
}
// Return len_a which is greater or
// equal to len_b
return len_a;
}
// The main function that performs AND
// operation of two-bit sequences
// and returns the resultant string
static string andOperationBitwise(string s1, string s2)
{
// Make both strings of same length with the
// maximum length of s1 & s2.
a = s1;
b = s2;
int length = makeEqualLength();
s1 = a;
s2 = b;
// Initialize res as NULL string
string res = "";
// We start from left to right as we have
// made both strings of same length.
for (int i = 0; i < length; i++) {
// Convert s1[i] and s2[i] to int and perform
// bitwise AND operation, append to "res" string
res = res
+ (char)((s1[i] - '0' & s2[i] - '0')
+ '0');
}
return res;
}
// Driver code
public static void Main(string[] args)
{
string[] arr = { "101", "110110", "111" };
int n = arr.Length;
string result = "";
// Check corner case: If there is just one
// binary string, then print it and return.
if (n < 2) {
Console.WriteLine(arr[n - 1]);
}
result = arr[0];
for (int i = 1; i < n; i++) {
result = andOperationBitwise(result, arr[i]);
}
Console.WriteLine(result);
}
}
// This code is contributed by phasing17
Javascript
<script>
// Javascript implementation of the above approach
// Helper method: given two unequal sized
// bit strings, converts them to
// same length by adding leading 0s in the
// smaller string. Returns the new length
let s1, s2;
function makeEqualLength()
{
let len_a = s1.length;
let len_b = s2.length;
let num_zeros = Math.abs(len_a - len_b);
if (len_a < len_b)
{
for(let i = 0; i < num_zeros; i++)
{
s1 = '0' + s1;
}
// Return len_b which is highest.
// No need to proceed further!
return len_b;
}
else
{
for(let i = 0; i < num_zeros; i++)
{
s2 = '0' + s2;
}
}
// Return len_a which is greater or
// equal to len_b
return len_a;
}
// The main function that performs AND
// operation of two-bit sequences
// and returns the resultant string
function andOperationBitwise()
{
// Make both strings of same length with the
// maximum length of s1 & s2.
let length = makeEqualLength();
// Initialize res as NULL string
let res = "";
// We start from left to right as we have
// made both strings of same length.
for(let i = 0 ; i<length; i++)
{
// Convert s1[i] and s2[i] to int
// and perform bitwise AND operation,
// append to "res" string
res = res + String.fromCharCode((s1[i].charCodeAt() -
'0'.charCodeAt() &
s2[i].charCodeAt() -
'0'.charCodeAt()) +
'0'.charCodeAt());
}
return res;
}
// Driver code
let arr = [ "101", "110110", "111" ];
let n = arr.length;
let result;
// Check corner case: If there is just one
// binary string, then print it and return.
if (n < 2)
{
document.write(arr[n - 1] + "</br>");
}
result = arr[0];
for(let i = 1; i<n; i++)
{
s1 = result;
s2 = arr[i];
result = andOperationBitwise();
}
document.write(result);
// This code is contributed by vaibhavrabadiya3
</script>
Producción:
000100
Enfoque 2: encuentre el tamaño de la cuerda más pequeña y más grande. Necesitamos esto para agregar ceros (más grande-más pequeño) a nuestro resultado. Por ejemplo, si tenemos 0010 y 11, entonces AND en estas strings será 0010 (ya que podemos escribir 11 como 0011). Luego realice la operación AND en cada bit.
Podemos lograr esto solo encontrando si el bit actual en cualquier string es 0 o no. Si el bit actual es 0 en cualquiera de las strings dadas, entonces la operación AND en ese bit será 0. Si todos los bits en la posición actual son 1, entonces la operación AND será 1.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the bitwise AND of
// all the binary strings
string strBitwiseAND(string* arr, int n)
{
string res;
// To store the largest and the smallest
// string's size, We need this to add '0's
// in the resultant string
int smallest_size = INT_MAX;
int largest_size = INT_MIN;
// Reverse each string
// Since we need to perform AND operation
// on bits from Right to Left
for (int i = 0; i < n; i++) {
reverse(arr[i].begin(), arr[i].end());
// Update the respective length values
smallest_size = min(smallest_size, (int)arr[i].size());
largest_size = max(largest_size, (int)arr[i].size());
}
// Traverse bits from 0 to smallest string's size
for (int i = 0; i < smallest_size; i++) {
bool all_ones = true;
for (int j = 0; j < n; j++) {
// If at this bit position, there is a 0
// in any of the given strings then AND
// operation on current bit position
// will be 0
if (arr[j][i] == '0') {
all_ones = false;
break;
}
}
// Add resultant bit to result
res += (all_ones ? '1' : '0');
}
// Add 0's to the string.
for (int i = 0; i < largest_size - smallest_size; i++)
res += '0';
// Reverse the string
// Since we started from LEFT to RIGHT
reverse(res.begin(), res.end());
// Return the resultant string
return res;
}
// Driver code
int main()
{
string arr[] = { "101", "110110", "111" };
int n = sizeof(arr) / sizeof(arr[0]);
cout << strBitwiseAND(arr, n);
return 0;
}
Java
// Java implementation of the above approach
class GfG
{
// Function to find the bitwise AND of
// all the binary strings
static String strBitwiseAND(String[] arr, int n)
{
String res = "";
// To store the largest and the smallest
// string's size, We need this to add
// '0's in the resultant string
int smallest_size = Integer.MAX_VALUE;
int largest_size = Integer.MIN_VALUE;
// Reverse each string
// Since we need to perform AND operation
// on bits from Right to Left
for (int i = 0; i < n; i++)
{
StringBuilder temp = new StringBuilder();
temp.append(arr[i]);
arr[i] = temp.reverse().toString();
// Update the respective length values
smallest_size = Math.min(smallest_size, arr[i].length());
largest_size = Math.max(largest_size, arr[i].length());
}
// Traverse bits from 0 to smallest string's size
for (int i = 0; i < smallest_size; i++)
{
boolean all_ones = true;
for (int j = 0; j < n; j++)
{
// If at this bit position, there is a 0
// in any of the given strings then AND
// operation on current bit position
// will be 0
if (arr[j].charAt(i) == '0')
{
all_ones = false;
break;
}
}
// Add resultant bit to result
res += (all_ones ? '1' : '0');
}
// Add 0's to the string.
for (int i = 0; i < largest_size - smallest_size; i++)
res += '0';
// Reverse the string
// Since we started from LEFT to RIGHT
StringBuilder temp = new StringBuilder();
temp.append(res);
res = temp.reverse().toString();
// Return the resultant string
return res;
}
// Driver code
public static void main(String []args)
{
String arr[] = { "101", "110110", "111" };
int n = arr.length;
System.out.println(strBitwiseAND(arr, n));
}
}
// This code is contributed by Rituraj Jain
Python3
# Python3 implementation of the above approach import sys; # Function to find the bitwise AND of # all the binary strings def strBitwiseAND(arr, n) : res = "" # To store the largest and the smallest # string's size, We need this to add '0's # in the resultant string smallest_size = sys.maxsize; largest_size = -(sys.maxsize - 1); # Reverse each string # Since we need to perform AND operation # on bits from Right to Left for i in range(n) : arr[i] = arr[i][::-1] ; # Update the respective length values smallest_size = min(smallest_size, len(arr[i])); largest_size = max(largest_size, len(arr[i])); # Traverse bits from 0 to smallest string's size for i in range(smallest_size) : all_ones = True; for j in range(n) : # If at this bit position, there is a 0 # in any of the given strings then AND # operation on current bit position # will be 0 if (arr[j][i] == '0') : all_ones = False; break; # Add resultant bit to result if all_ones : res += '1' ; else : res += '0' ; # Add 0's to the string. for i in range(largest_size - smallest_size) : res += '0'; # Reverse the string # Since we started from LEFT to RIGHT res = res[::-1]; # Return the resultant string return res; # Driver code if __name__ == "__main__" : arr = [ "101", "110110", "111" ]; n = len(arr) ; print(strBitwiseAND(arr, n)); # This code is contributed by Ryuga
C#
// C# implementation of the above approach:
using System;
class GfG
{
// Function to find the bitwise AND of
// all the binary strings
static String strBitwiseAND(String[] arr, int n)
{
String res = "";
// To store the largest and the smallest
// string's size, We need this to add
// '0's in the resultant string
int smallest_size = int.MaxValue;
int largest_size = int.MinValue;
// Reverse each string
// Since we need to perform AND operation
// on bits from Right to Left
String temp ="";
for (int i = 0; i < n; i++)
{
temp+=arr[i];
arr[i] = reverse(temp);
// Update the respective length values
smallest_size = Math.Min(smallest_size, arr[i].Length);
largest_size = Math.Max(largest_size, arr[i].Length);
}
// Traverse bits from 0 to smallest string's size
for (int i = 0; i < smallest_size; i++)
{
bool all_ones = true;
for (int j = 0; j < n; j++)
{
// If at this bit position, there is a 0
// in any of the given strings then AND
// operation on current bit position
// will be 0
if (arr[j][i] == '0')
{
all_ones = false;
break;
}
}
// Add resultant bit to result
res += (all_ones ? '1' : '0');
}
// Add 0's to the string.
for (int i = 0; i < largest_size - smallest_size; i++)
res += '0';
// Reverse the string
// Since we started from LEFT to RIGHT
String temp1 = "";
temp1+=res;
res = reverse(temp1);
// Return the resultant string
return res;
}
static String reverse(String input)
{
char[] temparray = input.ToCharArray();
int left, right = 0;
right = temparray.Length - 1;
for (left = 0; left < right; left++, right--)
{
// Swap values of left and right
char temp = temparray[left];
temparray[left] = temparray[right];
temparray[right] = temp;
}
return String.Join("",temparray);
}
// Driver code
public static void Main(String []args)
{
String []arr = { "101", "110110", "111" };
int n = arr.Length;
Console.WriteLine(strBitwiseAND(arr, n));
}
}
// This code has been contributed by 29AjayKumar
Javascript
<script>
// JavaScript implementation of the above approach:
// Function to find the bitwise AND of
// all the binary strings
function strBitwiseAND(arr, n)
{
let res = "";
// To store the largest and the smallest
// string's size, We need this to add
// '0's in the resultant string
let smallest_size = Number.MAX_VALUE;
let largest_size = Number.MIN_VALUE;
// Reverse each string
// Since we need to perform AND operation
// on bits from Right to Left
let temp ="";
for (let i = 0; i < n; i++)
{
temp+=arr[i];
arr[i] = reverse(temp);
// Update the respective length values
smallest_size = Math.min(smallest_size, arr[i].length);
largest_size = Math.max(largest_size, arr[i].length);
}
// Traverse bits from 0 to smallest string's size
for (let i = 0; i < smallest_size; i++)
{
let all_ones = true;
for (let j = 0; j < n; j++)
{
// If at this bit position, there is a 0
// in any of the given strings then AND
// operation on current bit position
// will be 0
if (arr[j][i] == '0')
{
all_ones = false;
break;
}
}
// Add resultant bit to result
res += (all_ones ? '1' : '0');
}
// Add 0's to the string.
for (let i = 0; i < largest_size - smallest_size; i++)
res += '0';
// Reverse the string
// Since we started from LEFT to RIGHT
let temp1 = "";
temp1+=res;
res = reverse(temp1);
// Return the resultant string
let temparray1 = res;
let Temparray = "";
for(let i = 6; i < temparray1.length; i++)
{
Temparray = Temparray + temparray1[i];
}
return Temparray;
}
function reverse(input)
{
let temparray = input.split('');
let left, right = 0;
right = temparray.length - 1;
for (left = 0; left < right; left++, right--)
{
// Swap values of left and right
let temp = temparray[left];
temparray[left] = temparray[right];
temparray[right] = temp;
}
return temparray.join("");
}
let arr = [ "101", "110110", "111" ];
let n = arr.length;
document.write(strBitwiseAND(arr, n));
</script>
Producción:
000100
Publicación traducida automáticamente
Artículo escrito por Aashish Chauhan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA