计算按位且其元素等于零的子数组

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) 时间内使用滑动 window。

如果我们知道索引 [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]

我们将遍历滑动 window 的 right 端，同时存储最小的 left 端（即最大的 window），这样 A[left, left + 1, ... right] 有一个非零按位 &。请注意，此 left 端只能随着右端的增加而增加。

要更新我们的window，我们需要

能够用 A[right] 获得我们 window 的 &（简单）
能够从我们的 window 中删除 A[left] 的 &（困难）

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

下面是示例数组中最大非零值 windows 的演练：

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

此处，非零 & window 大小的总和为 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

N.B。假设整数的最大值 bit-width 是常数。要在整数可以任意大时获得 linear-time 解决方案，您需要保留一个 meta-counter，它跟踪设置位的计数。

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

计算按位且其元素等于零的子数组

Count the Subarray's which has bitwise and of its elements equal to Zero

python

algorithm

bit-manipulation

list

bitwise-operators