Tanya operasi bitwise ATAU tatasusunan yang diberikan dalam julat indeks menggunakan C++

Dalam artikel ini, kami diberikan pelbagai integer. Tugas kami ialah mencari bitwise ATAU semua nombor dalam julat tertentu, contohnya,

Input: arr[] = {1, 3, 1, 2, 3, 4}, q[] = {{0, 1}, {3, 5}}
Output:
3
7
1 OR 3 = 3
2 OR 3 OR 4 = 7
Input: arr[] = {1, 2, 3, 4, 5}, q[] = {{0, 4}, {1, 3}}
Output:
7
7

Dalam masalah yang diberikan, kami akan menggunakan pendekatan kekerasan untuk menyelesaikannya dan kemudian menyemak sama ada ia boleh digunakan pada kekangan yang lebih tinggi. Jika tidak, maka kami akan mengoptimumkan kaedah kami agar sesuai dengan kekangan yang lebih tinggi.

Kaedah Brute Force

Dalam kaedah ini kita hanya melingkari setiap julat dan mengira bitwise atau semua nombor dalam julat itu dan mencetak jawapan kita.

Contoh

#include <bits/stdc++.h>
using namespace std;
int main() {
   int arr[] = { 7, 5, 3, 5, 2, 3 };
   int n = sizeof(arr) / sizeof(int); // size of our array
   int queries[][2] = { { 1, 3 }, { 4, 5 } }; // 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 = 0;
      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

7
3

Kerumitan masa pendekatan ini ialah O(N*Q) dengan N ialah saiz tatasusunan dan Q ialah bilangan pertanyaan sekarang, kerana anda boleh lihat kerumitan ini tidak terpakai untuk kekangan yang lebih tinggi, jadi sekarang kami akan mengoptimumkan kaedah kami supaya ia juga berfungsi untuk kekangan yang lebih tinggi.

Kaedah yang cekap

Dalam kaedah ini kita akan mengira bilangan digit awalan dan kemudian menyemak sama ada nombor itu mempunyai set bit tertentu. Jika ya, maka kami meletakkan perkara ini ke dalam jawapan jika tidak, kami menyimpan perkara ini.

Contoh

#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 != 0)
         ans = (ans | (1LL << i));
   }
   return ans;
}
int main() {
   int arr[] = {7, 5, 3, 5, 2, 3};
   int n = sizeof(arr) / sizeof(int); // size of our array
   bitcount(arr, n);
   int queries[][2] = {{1, 3}, {4, 5}}; // 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

7
3

Kerumitan masa kaedah ini ialah O(N), dengan N ialah saiz tatasusunan, jadi kaedah ini boleh disesuaikan dengan kekangan yang lebih tinggi.

Penjelasan kod di atas

Dalam kaedah ini kita mengira bilangan digit awalan dan menyimpannya. Sekarang kita mengira pertanyaan di mana kita mengulangi kiraan awalan itu dan mengalih keluar kiraan bit l-1 supaya kita mempunyai kiraan bit nombor dalam julat [l, r] kerana kita tahu jika bit ditetapkan dalam sebarang nombor oleh itu, Jika anda bitwise ATAU ia dengan mana-mana nombor lain maka bit akan kekal ditetapkan jadi menggunakan sifat bitwise ini ATAU kami menyemak sama ada kiraan bit bukan sifar yang bermaksud terdapat nombor dalam julat dengan bit yang ditetapkan, jadi kami tetapkan sedikit jawapan dan teruskan gelung, akhirnya mencetak jawapan.

Kesimpulan

Artikel ini menyelesaikan masalah pengiraan bitwise ATAU pertanyaan dalam julat indeks [L, R] yang diberikan tatasusunan. Kami juga mempelajari program C++ untuk menyelesaikan masalah ini dan cara lengkap untuk menyelesaikan masalah ini (biasa dan cekap). Kita boleh menulis program yang sama dalam bahasa lain seperti C, java, python dan bahasa lain. Kami berharap artikel ini dapat membantu anda.

Atas ialah kandungan terperinci Tanya operasi bitwise ATAU tatasusunan yang diberikan dalam julat indeks menggunakan C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!