假设我们有一个数字列表
[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)如果我们知道索引
A[L, R]&[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]
我们将迭代滑动窗口的
rightleftA[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的问题；这需要更多的工作。
代码：
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;
}