累积按位运算 [英] Cumulative bitwise operations

问题描述

假设您有一个数组 A = [x，y，z，...]

然后您计算一个前缀/累积的BITWISE-OR数组 P = [x，x | y，x | y | z，...]

And then you compute a prefix/cumulative BITWISE-OR array P = [x, x | y, x | y | z, ... ]

如果我想找到索引 1 <之间的元素的BITWISE-OR， / code>和索引 6 ，如何使用此预先计算的 P 数组来做到这一点？

If I want to find the BITWISE-OR of the elements between index 1 and index 6, how can I do that using this precomputed P array? Is it possible?

我知道它可以在累加总和中工作以获取一定范围内的总和，但是我不确定使用位运算。

I know it works in cumulative sums for getting sum in a range, but I am not sure with bit operations.

编辑：： A 中允许重复，因此 A = [1、1、2 ，2，2，2，3] 是可能的。

duplicates ARE allowed in A, so A = [1, 1, 2, 2, 2, 2, 3] is a possibility.

推荐答案

无法使用前缀/累积BITWISE-OR数组来计算某个随机范围的按位或，您可以尝试使用2个元素的简单情况并验证自己。

There is impossible to use prefix/cumulative BITWISE-OR array to calculate the Bitwise-or of some random range, you can try with a simple case of 2 elements and verify yourself.

但是

假设我们正在处理32位整数，我们知道，对于范围x的按位或到y，如果范围（x，y）中有一个 ith ith 位将为1 $ c>位为1。因此，通过反复回答以下查询：

Assuming that we are dealing with 32 bit integer, we know that, for the bitwise-or sum from range x to y, the ith bit of the result will be 1 if there exists a number in range (x,y) that has ith bit is 1. So by answering this query repeatedly:

• 在（x，y）范围内是否有任何数字具有 ith 位设置为1？

• Is there any number in range (x, y) that has ith bit set to 1?

我们可以形成问题的答案。

We can form the answer to the question.

因此，如何检查范围（x，y）中是否至少有一个数字 ith 设置？我们可以预处理并填充数组 pre [n] [32] ，其中包含数组中所有32位的前缀和。

So how to check that in range (x, y), there is at least a number that has bit ith set? we can preprocess and populate the array pre[n][32]which contain the prefix sum of all 32 bit within the array.

for(int i = 0; i < n; i++){
   for(int j = 0; j < 32; j++){
       //check if bit i is set for arr[i]
       if((arr[i] && (1 << j)) != 0){
           pre[i][j] = 1;
       }
       if( i > 0) {
           pre[i][j] += pre[i - 1][j];
       }
   }
}

然后，检查是否 i 被设置为范围（x，y）等于检查是否：

And, to check if bit i is set form range (x, y) is equalled to check if:

pre[y][i] - pre[x - 1][i] > 0

重复此检查32次以计算最终结果：

Repeat this check 32 times to calculate the final result:

int result = 0;
for (int i = 0; i < 32; i++){
   if((pre[y][i] - (i > 0 ? pre[x - 1][i] : 0)) > 0){
       result |= (1 << i);
   }
}
return result;

这篇关于累积按位运算的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！