Dadas dos strings binarias A y B de longitud N y M (hasta 10 5 ). La tarea es repetir el siguiente proceso y encontrar la respuesta.
Initialize ans = 0
while (B > 0)
ans += A & B (bitwise AND)
B = B / 2
print ans
Nota: La respuesta puede ser muy grande, así que imprima Respuesta % 1000000007 .
Ejemplos:
Input: A = "1001", B = "10101" Output: 11 1001 & 10101 = 1, ans = 1, B = 1010 1001 & 1010 = 8, ans = 9, B = 101 1001 & 101 = 1, ans = 10, B = 10 1001 & 10 = 0, ans = 10, B = 1 1001 & 1 = 1, ans = 11, B = 0 Input: A = "1010", B = "1101" Output: 12
Enfoque: dado que solo B se ve afectado en todas las iteraciones y dividir un número binario por 2 significa desplazarlo 1 bit a la derecha, se puede observar que un bit en A solo se verá afectado por los bits establecidos en B que están en el izquierdo, es decir, más significativo que el bit actual (incluido el bit actual). Por ejemplo, A = «1001» y B = «10101» , el bit menos significativo en A solo se verá afectado por los bits establecidos en B , es decir , 3 bits en total y el bit más significativo en A solo se verá afectado por un solo establecer un bit en B , es decir, elbit más significativo en B ya que todos los demás bits establecidos no lo afectarán en ninguna iteración del bucle mientras se realiza AND bit a bit , por lo que el resultado final será 2 0 * 3 + 2 3 * 1 = 3 + 8 = 11 .
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod (int)(1e9 + 7)
// Function to return the required result
ll BitOperations(string a, int n, string b, int m)
{
// Reverse the strings
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
// Count the number of set bits in b
int c = 0;
for (int i = 0; i < m; i++)
if (b[i] == '1')
c++;
// To store the powers of 2
ll power[n];
power[0] = 1;
// power[i] = pow(2, i) % mod
for (int i = 1; i < n; i++)
power[i] = (power[i - 1] * 2) % mod;
// To store the final answer
ll ans = 0;
for (int i = 0; i < n; i++) {
if (a[i] == '1') {
// Add power[i] to the ans after
// multiplying it with the number
// of set bits in b
ans += c * power[i];
if (ans >= mod)
ans %= mod;
}
// Divide by 2 means right shift b>>1
// if b has 1 at right most side than
// number of set bits will get decreased
if (b[i] == '1')
c--;
// If no more set bits in b i.e. b = 0
if (c == 0)
break;
}
// Return the required answer
return ans;
}
// Driver code
int main()
{
string a = "1001", b = "10101";
int n = a.length(), m = b.length();
cout << BitOperations(a, n, b, m);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
static int mod = (int)(1e9 + 7);
// Function to return the required result
static int BitOperations(String a,
int n, String b, int m)
{
// Reverse the strings
char[] ch1 = a.toCharArray();
reverse( ch1 );
a = new String( ch1 );
char[] ch2 = b.toCharArray();
reverse( ch2 );
b = new String( ch2 );
// Count the number of set bits in b
int c = 0;
for (int i = 0; i < m; i++)
if (b.charAt(i) == '1')
c++;
// To store the powers of 2
int[] power = new int[n];
power[0] = 1;
// power[i] = pow(2, i) % mod
for (int i = 1; i < n; i++)
power[i] = (power[i - 1] * 2) % mod;
// To store the final answer
int ans = 0;
for (int i = 0; i < n; i++)
{
if (a.charAt(i) == '1')
{
// Add power[i] to the ans after
// multiplying it with the number
// of set bits in b
ans += c * power[i];
if (ans >= mod)
ans %= mod;
}
// Divide by 2 means right shift b>>1
// if b has 1 at right most side than
// number of set bits will get decreased
if (b.charAt(i) == '1')
c--;
// If no more set bits in b i.e. b = 0
if (c == 0)
break;
}
// Return the required answer
return ans;
}
static void reverse(char a[])
{
int i, k,n=a.length;
char t;
for (i = 0; i < n / 2; i++)
{
t = a[i];
a[i] = a[n - i - 1];
a[n - i - 1] = t;
}
}
// Driver code
public static void main(String[] args)
{
String a = "1001", b = "10101";
int n = a.length(), m = b.length();
System.out.println(BitOperations(a, n, b, m));
}
}
// This code contributed by Rajput-Ji
Python3
# Python 3 implementation of the approach mod = 1000000007 # Function to return the required result def BitOperations(a, n, b, m): # Reverse the strings a = a[::-1] b = b[::-1] # Count the number of set # bits in b c = 0 for i in range(m): if (b[i] == '1'): c += 1 # To store the powers of 2 power = [None] * n power[0] = 1 # power[i] = pow(2, i) % mod for i in range(1, n): power[i] = (power[i - 1] * 2) % mod # To store the final answer ans = 0 for i in range(0, n): if (a[i] == '1'): # Add power[i] to the ans after # multiplying it with the number # of set bits in b ans += c * power[i] if (ans >= mod): ans %= mod # Divide by 2 means right shift b>>1 # if b has 1 at right most side than # number of set bits will get decreased if (b[i] == '1'): c -= 1 # If no more set bits in b i.e. b = 0 if (c == 0): break # Return the required answer return ans # Driver code if __name__ == '__main__': a = "1001" b = "10101" n = len(a) m = len(b) print(BitOperations(a, n, b, m)) # This code is contributed by # Surendra_Gangwar
C#
// C# implementation of the approach
using System;
using System.Collections;
class GFG
{
static int mod = (int)(1e9 + 7);
// Function to return the required result
static int BitOperations(string a,
int n, string b, int m)
{
// Reverse the strings
char[] ch1 = a.ToCharArray();
Array.Reverse( ch1 );
a = new string( ch1 );
char[] ch2 = b.ToCharArray();
Array.Reverse( ch2 );
b = new string( ch2 );
// Count the number of set bits in b
int c = 0;
for (int i = 0; i < m; i++)
if (b[i] == '1')
c++;
// To store the powers of 2
int[] power = new int[n];
power[0] = 1;
// power[i] = pow(2, i) % mod
for (int i = 1; i < n; i++)
power[i] = (power[i - 1] * 2) % mod;
// To store the final answer
int ans = 0;
for (int i = 0; i < n; i++)
{
if (a[i] == '1')
{
// Add power[i] to the ans after
// multiplying it with the number
// of set bits in b
ans += c * power[i];
if (ans >= mod)
ans %= mod;
}
// Divide by 2 means right shift b>>1
// if b has 1 at right most side than
// number of set bits will get decreased
if (b[i] == '1')
c--;
// If no more set bits in b i.e. b = 0
if (c == 0)
break;
}
// Return the required answer
return ans;
}
// Driver code
static void Main()
{
string a = "1001", b = "10101";
int n = a.Length, m = b.Length;
Console.WriteLine(BitOperations(a, n, b, m));
}
}
// This code is contributed by mits
PHP
<?php
// PHP implementation of the approach
$GLOBALS['mod'] = (1e9 + 7);
// Function to return the required result
function BitOperations($a, $n, $b, $m)
{
// Reverse the strings
$a = strrev($a);
$b = strrev($b);
// Count the number of set bits in b
$c = 0;
for ($i = 0; $i < $m; $i++)
if ($b[$i] == '1')
$c++;
# To store the powers of 2
$power = array() ;
$power[0] = 1;
// power[i] = pow(2, i) % mod
for ($i = 1; $i < $n; $i++)
$power[$i] = ($power[$i - 1] * 2) %
$GLOBALS['mod'];
// To store the final answer
$ans = 0;
for ($i = 0; $i < $n; $i++)
{
if ($a[$i] == '1')
{
// Add power[i] to the ans after
// multiplying it with the number
// of set bits in b
$ans += $c * $power[$i];
if ($ans >= $GLOBALS['mod'])
$ans %= $GLOBALS['mod'];
}
// Divide by 2 means right shift b>>1
// if b has 1 at right most side than
// number of set bits will get decreased
if ($b[$i] == '1')
$c--;
// If no more set bits in b i.e. b = 0
if ($c == 0)
break;
}
// Return the required answer
return $ans;
}
// Driver code
$a = "1001";
$b = "10101";
$n = strlen($a);
$m = strlen($b);
echo BitOperations($a, $n, $b, $m);
// This code is contributed by Ryuga
?>
Javascript
<script>
// JavaScript implementation of the approach
let mod = (1e9 + 7);
// Function to return the required result
function BitOperations(a, n, b, m)
{
// Reverse the strings
let ch1 = a.split('');
ch1.reverse();
a = ch1.join("");
let ch2 = b.split('');
ch2.reverse();
b = ch2.join("");
// Count the number of set bits in b
let c = 0;
for (let i = 0; i < m; i++)
if (b[i] == '1')
c++;
// To store the powers of 2
let power = new Array(n);
power[0] = 1;
// power[i] = pow(2, i) % mod
for (let i = 1; i < n; i++)
power[i] = (power[i - 1] * 2) % mod;
// To store the final answer
let ans = 0;
for (let i = 0; i < n; i++)
{
if (a[i] == '1')
{
// Add power[i] to the ans after
// multiplying it with the number
// of set bits in b
ans += c * power[i];
if (ans >= mod)
ans %= mod;
}
// Divide by 2 means right shift b>>1
// if b has 1 at right most side than
// number of set bits will get decreased
if (b[i] == '1')
c--;
// If no more set bits in b i.e. b = 0
if (c == 0)
break;
}
// Return the required answer
return ans;
}
let a = "1001", b = "10101";
let n = a.length, m = b.length;
document.write(BitOperations(a, n, b, m));
</script>
Producción:
11
Complejidad temporal: O(m + n)
Espacio Auxiliar: O(n)
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA