Given two binary strings perform operation until B > 0 and print the result

0 0 8 minutes read

Given two binary strings A and B of length N and M (up to 10⁵). The task is to repeat the below process and find the answer.

Initialize ans = 0
while (B > 0)
    ans += A & B (bitwise AND)
    B = B / 2
print ans

Note: Answer can be very large so print Answer % 1000000007.
Examples:

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

Approach: Since only B is getting affected in all the iterations and dividing a binary number by 2 means right shifting it by 1 bit, it can be observed that a bit in A will only be affected by the set bits in B which are on the left i.e. more significant than the current bit (including the current bit). For example, A = “1001” and B = “10101”, the least significant bit in A will only be affected by the set bits in B i.e. 3 bits in total and the most significant bit in A will only be affected by a single set bit in B i.e. the most significant bit in B as all the other set bits will not affect it in any iteration of the loop while performing bitwise AND, so the final result will be 2⁰ * 3 + 2³ * 1 = 3 + 8 = 11.
Below is the implementation of the above approach.

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>

Output:

Time Complexity: O(m + n)

Auxiliary Space: O(n)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!