计算按位 和 元素的个数等于 0 的子数组

Question

假设我们有一个数字列表，

[7,2,9,8,6,12,109,28,14,19]

我想找到一种有效的方法来计算该列表的所有子列表，这些子列表将按位且等于零，

例如：

[2,5] # 2&5 = 0
[9,5,7,2] # 9&5&7&2 = 0

如果有人知道如何最有效地做到这一点，请告诉我

Answer 1

您可以使用滑动窗口在 O(n) 时间内完成此操作。

如果我们知道索引 [L, R] 上的 A 子数组的 & 为零，那么我们就知道所有较大的子数组([L, R + 1], [L, R + 2], [L, R + 3], ...)由于以下原因， & 也将为零包含下&的单调性。

例如，从左侧计算数组的部分 & 乘积：

Array (Base 10): [  7,  3,   10,   5]

Array (Binary) : [111, 11, 1010, 101]

Partial &s     : [111, 11,   10,   0]

---

我们将迭代滑动窗口的 右 端，同时存储最小的 left 端（即最大窗口），使得 A[left, left + 1, ... right] 具有非零按位 &。请注意，此左端只能随着右端的增加而增加。

要更新我们的窗口，我们需要

1. 能够使用 A[right] 获取窗口的 & （简单）
2. 能够删除 & of A[left] from our window (hard)

为了有效地进行删除，我们将跟踪窗口中所有元素的设置位计数每个位的位置。这让我们可以在窗口中添加和删除元素，并通过测试每个设置位位置的计数是否小于窗口的长度来测试窗口的 & 是否为零。

以下是示例数组上最大非零窗口的演练：

Base 10:
A = [7, 2, 9, 8, 6, 12, 109, 28, 14, 19]

Binary:
111, 10, 1001, 1000, 110, 1100, 1101101, 11100, 1110, 10011


Maximal nonzero [windows] at each right endpoint:


--------------------------------------------------------------
[111], 10, 1001, 1000, 110, 1100, 1101101, 11100, 1110, 10011
^   ^

left = 0, right = 0, size = 1



--------------------------------------------------------------
[111, 10], 1001, 1000, 110, 1100, 1101101, 11100, 1110, 10011
^       ^

left = 0, right = 1, size = 2



--------------------------------------------------------------
111, 10, [1001], 1000, 110, 1100, 1101101, 11100, 1110, 10011
         ^    ^                                         

left = 2, right = 2, size = 1



--------------------------------------------------------------
111, 10, [1001, 1000], 110, 1100, 1101101, 11100, 1110, 10011
         ^          ^                                         

left = 2, right = 3, size = 2



--------------------------------------------------------------
111, 10, 1001, 1000, [110], 1100, 1101101, 11100, 1110, 10011
                     ^   ^

left = 4, right = 4, size = 1



--------------------------------------------------------------
111, 10, 1001, 1000, [110, 1100], 1101101, 11100, 1110, 10011
                     ^         ^

left = 4, right = 5, size = 2



--------------------------------------------------------------
111, 10, 1001, 1000, [110, 1100, 1101101], 11100, 1110, 10011
                     ^                  ^

left = 4, right = 6, size = 3



--------------------------------------------------------------
111, 10, 1001, 1000, [110, 1100, 1101101, 11100], 1110, 10011
                     ^                         ^

left = 4, right = 7, size = 4



--------------------------------------------------------------
111, 10, 1001, 1000, [110, 1100, 1101101, 11100, 1110], 10011
                     ^                               ^   

left = 4, right = 8, size = 5



--------------------------------------------------------------
111, 10, 1001, 1000, 110, 1100, 1101101, 11100, [1110, 10011]
                                                ^           ^   

left = 8, right = 9, size = 2

此处，非零& 窗口大小的总和为23。由于长度 10 数组有 55 个可能的子数组，因此答案为 55 - 23 = 32 按位-& - 零子数组。

Python 代码：

def count_bitwise_and_zero(nums: List[int]) -> int:
    """Count nonempty subarrays with & of elements equal to 0.
    Given a list on nonnegative integers,
    returns the number of contiguous, nonempty subarrays for which the
    bitwise and of all elements in the subarray are equal to 0.

    Runs in linear time on fixed-width integers.
    """

    def get_set_bit_indices(x: int) -> List[int]:
        """Return indices of set bits in x"""
        pow_2 = 1
        exponent = 0
        set_bits = []

        while pow_2 <= x:
            if pow_2 & x != 0:
                set_bits.append(exponent)

            exponent += 1
            pow_2 *= 2

        return set_bits

    def is_bitwise_and_zero(window_length: int, bit_counts: Dict[int, int]) -> bool:
        """Given bit counts for a window of an array, return whether the
        window's elements have bitwise AND equal to zero."""
        return all(value < window_length for value in bit_counts.values())

    n = len(nums)
    total_subarray_count = n * (n + 1) // 2

    nonzero_subarray_count = 0
    window_bit_counts = Counter()

    """At every iteration start, [left_idx, right_idx] is the longest subarray
    ending at right_idx whose bitwise AND is nonzero."""
    left_idx = 0

    for right_idx, right_element in enumerate(nums):
        if right_element == 0:
            window_bit_counts.clear()
            left_idx = right_idx + 1
            continue

        # Expand window to include right
        window_bit_counts += Counter(get_set_bit_indices(right_element))

        # Shrink window until AND is nonzero
        while (left_idx < right_idx
               and is_bitwise_and_zero(right_idx - left_idx + 1, window_bit_counts)):

            window_bit_counts -= Counter(get_set_bit_indices(nums[left_idx]))
            left_idx += 1

        nonzero_subarray_count += (right_idx - left_idx + 1)

    return total_subarray_count - nonzero_subarray_count

用法示例：

count_bitwise_and_zero([7, 2, 9, 8, 6, 12, 109, 28, 14, 19])
>>> 32

注意：假设整数的最大位宽是常量。当整数可以任意大时，为了获得线性时间解决方案，您需要保留一个元计数器，它跟踪设置位的计数。

作为练习，您可以尝试推广到按位 & 等于某个可能大于零的目标 t 的问题；这需要更多的工作。

Answer 2

我们可以使用前缀和和二分查找来解决它。
步骤 1 .首先我们创建一个大小为 n*32 的数组（假设数字小于 2^32）并获取第 i 位集的前缀和。
然后应用二分查找。

代码 ：

void solved(){ 
int n;
cin>>n;
vector<int> v(n);
for(int i=0;i<n;i++){
    cin>>v[i];
}

vector<vector<int>> pre(n+1,vector<int>(32,0));

for(int i=0;i<n;i++){
    for(int j=0;j<32;j++){
        if((v[i]>>j)&1){
            pre[i+1][j] = 1;
        }
    }
}
for(int i=1;i<=n;i++){
    for(int j=0;j<32;j++){
        pre[i][j] += pre[i-1][j];
    }
}

int total = 0;

for(int i=1;i<=n;i++){
    int lo = i;
    int hi = n;
    int ans = -1;
    while(lo<=hi){
        
        int mid = (lo+hi)/2;
        int len = mid-i+1;
        bool isok = true;
        for(int j=0;j<32;j++){
            int x = pre[mid][j] - pre[i-1][j];
            if(x == len){
                isok = false;
            }
        }
        
        if(isok){
            ans = mid;
            hi = mid-1;
        }else{
            lo = mid+1;
        }
    }
    if(ans != -1){
        if(ans == i)ans++;
        total += (n-ans+1);
    }
}
cout<<total<<endl;
}