假设我们有一个数字列表
[7,2,9,8,6,12,109,28,14,19]
我想找到一种有效的方法来计算这个列表的所有子列表，它将具有逐位且等于零的
类似：
[2,5] # 2&5 = 0
[9,5,7,2] # 9&5&7&2 = 0
如果有人知道如何最有效地进行，请告诉我
您可以使用滑动窗口在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]
我们将在滑动窗口的right端上迭代，同时存储最小的left端(即最大窗口(，使得A[left, left + 1, ... right]具有非零位&。注意，这个left端只能随着右端的增加而增加。
要更新我们的窗口，我们需要
- 能够用
A[right]拍摄我们窗户的&(简单( - 能够从我们的窗口中删除
A[left]的&(硬(
为了有效地进行删除，我们将跟踪窗口中每个位位置的所有元素的集合位计数。这使我们可以在窗口中添加和删除元素，并通过测试每个设置位位置的计数是否小于窗口长度来测试窗口的&是否为零。
以下是示例数组上最大非零窗口的演练：
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的问题，该目标可能大于零；这需要更多的工作。