Using C++, translate the following into Chinese: Query for bitwise AND within the index range of a given array

In this article we are given a problem where given an array of integers our task is to find the bitwise AND of a given range e.g. 7minus;

Input: arr[ ] = {1, 3, 1, 2, 32, 3, 3, 4, 4}, q[ ] = {{0, 1}, {3, 5}}
Output:
1
0 0
1 AND 31 = 1
23 AND 34 AND 4 = 00
Input: arr[ ] = {1, 2, 3, 4, 510, 10 , 12, 16, 8}, q[ ] = {{0, 42}, {1, 33, 4}}
Output:
0 8
0

We will first apply the brute force method and check its time complexity. If our time complexity is not good enough, we try to develop a better method.

Brute force method

In the given method, we will iterate through the given range and find our method answer and print it.

Example

#include <bits/stdc++.h>
using namespace std;
int main() {
   int ARR[] = { 10, 10 , 12, 16, 8 };
   int n = sizeof(ARR) / sizeof(int); // size of our array
   int queries[][2] = { {0, 2}, {3, 4} }; // given queries
   int q = sizeof(queries) / sizeof(queries[0]); // number of queries
   for(int i = 0; i < q; i++) { // traversing through all the queries
      long ans = 1LL << 32;
      ans -= 1; // making all the bits of ans 1
      for(int j = queries[i][0]; j <= queries[i][1]; j++) // traversing through the range
         ans &= ARR[j]; // calculating the answer
      cout << ans << "\n";
   }
   return 0;
}

Output

8
0

In this approach we run a loop on each range of the query and print their set bitwise, so our program The overall complexity becomes O(N*Q), where N is the size of the array and Q is the number of queries we have now, you can see that this complexity does not lend itself to higher constraints, so We will propose a faster method for this problem.

Efficient method h2>

In this problem, we pre-calculate the number of prefix digits of the array and calculate the bitwise AND of the given range by checking the contribution of the set bits in the given range.

Example

#include <bits/stdc++.h>
using namespace std;
#define bitt 32
#define MAX (int)10e5
int prefixbits[bitt][MAX];
void bitcount(int *ARR, int n) { // making prefix counts
   for (int j = 31; j >= 0; j--) {
      prefixbits[j][0] = ((ARR[0] >> j) & 1);
      for (int i = 1; i < n; i++) {
         prefixbits[j][i] = ARR[i] & (1LL << j);
         prefixbits[j][i] += prefixbits[j][i - 1];
      }
   }
   return;
}

int check(int l, int r) { // calculating the answer
   long ans = 0; // to avoid overflow we are taking ans as long
   for (int i = 0; i < 32; i++){
      int x;
      if (l == 0)
         x = prefixbits[i][r];
      else
         x = prefixbits[i][r] - prefixbits[i][l - 1];
      if (x == r - l + 1)
         ans = ans | 1LL << i;
      }
   return ans;
}
int main() {
   int ARR[] = { 10, 10 , 12, 16, 8 };
   int n = sizeof(ARR) / sizeof(int); // size of our array
   memset(prefixbits, 0, sizeof(prefixbits)); // initializing all the elements with 0
   bitcount(ARR, n);
   int queries[][2] = {{0, 2}, {3, 4}}; // given queries
   int q = sizeof(queries) / sizeof(queries[0]); // number of queries
   for (int i = 0; i < q; i++) {
      cout << check(queries[i][0], queries[i][1]) << "\n";
   }
   return 0;
}

Output

2
0

In this approach we use constant time to compute the query thereby reducing the time complexity from O(N* Q) is greatly reduced to O(N), where N is now the size of the given array. The procedure can also be adapted to higher constraints.

Explanation of the above code

In this method, we count all the prefix digits and store them in the index. Now, when we calculate the query, we just need to check if the count of a certain bit is the same as the number of elements present in the range. If yes, we set this bit to 1 in x, if no, we leave the bit as if any number present in the given range has that bit 0, so the entire bitwise AND of that bit will be zero, This is how we are computing the bitwise AND.

Conclusion

In this article, we solved the problem of enumerating all queries bitwise ANDed in a given index range [L, R] over a large batch. We also learned a C program to solve this problem and a complete way to solve this problem (normal and efficient). We can write the same program in other languages ​​such as C, java, python and other languages. We hope this article was helpful to you.

The above is the detailed content of Using C++, translate the following into Chinese: Query for bitwise AND within the index range of a given array. For more information, please follow other related articles on the PHP Chinese website!