用目标按位与值查找子数组 [英] Finding subarray with target bitwise AND value

问题描述

给出大小为 N 的数组 A 和整数 P ，找到子数组 B = A [i ... j] ，使 i< = j ，计算子数组元素的按位值，例如 K = B [i]& B [i + 1]& ...& B [j] 。

输出 | KP | 的最小值> K 。

解决方案

这里还有另一种准线性算法，混合了

因此您可以计算 A [i]& A [i + 1]& ...& A [I + N-1] 仅执行 log N 个操作。

这里是管理计数器的方式：如果

• 计数器是 C0，C1，... Cp 和


• Ck 是 Ck0，Ck1，... Ckm ，

然后 Cpq ... C1q，C0q 是 {A [i]，A [i + 1]，...，A [j-1]} 。

位级实现（在python中）；所有位都是并行管理的。

  def add（counter，x）：
k = 0 
而x：
x，计数器[k] = x& counter [k]，x ^ counter [k] 
k + = 1 
 
 def sub（counter，x）：
k = 0 
而x：
x，counter [k] = x& 〜counter [k]，x ^ counter [k] 
 k + = 1 
 
 def val（counter，count）：＃return A [i]& ....&如果count = j-i，则为A [j-1]。 
 k = 0 
 res = -1 
而计数：
如果计数％2> 0：res& =计数器[k] 
其他：res& =〜counter [k] 
计数// = 2 
k + = 1 
返回res 
  

和算法：

  defsolve（A，P）：
计数器= np.zeros（32，np.int64）＃最多4Go 
n = A.size 
i = j = 0 
 K = P＃触发填充缓冲区
 mini = np.int64（2 ** 63-1）
 
而i  
如果K < P或j == n：＃转储缓冲区
 sub（counter，A [i]）
i + = 1 
 else：＃填充缓冲区
 add（counter，A [j ]）
j + = 1 
 
如果j> i：
 K = val（计数器，计数）
 X = np.abs（K-P）$ b如果mini>为$ b X：mini = X 
 else：K = P＃重置K 
 
 return mini 
  

val ， sub 和 add 是 O（ln N），因此整个过程是 O（N ln N）

测试：

  n = 10 ** 5 
 A = np.random。 randint（0，10 ** 8，n，dtype = np.int64）
 P = np.random.randint（0，10 ** 8，dtype = np.int64）
 
 ％timesolve（A，P）
墙壁时间：0.8 s 
出：452613036735 
  

numba编译版本（用 @ numba.jit 装饰4个函数）快了200倍（5毫秒）。

Given an array A of size N and an integer P, find the subarray B = A[i...j] such that i <= j, compute the bitwise value of subarray elements say K = B[i] & B[i + 1] & ... & B[j].
Output the minimum value of |K-P| among all possible values of K.

解决方案

Here an other quasi-linear algorithm, mixing the yonlif Find subarray with given sum problem solution with Harold idea to compute K[i,j]; therefore I don't use pre-processing which if memory-hungry. I use a counter to keep trace of bits and compute at most 2N values of K, each costing at most O(log N). since log N is generally smaller than the word size (B), it's faster than a linear O(NB) algorithm.

Counts of bits of N numbers can be done with only ~log N words :

So you can compute A[i]&A[i+1]& ... &A[I+N-1] with only log N operations.

Here the way to manage the counter: if

• counter is C0,C1, ...Cp, and
• Ck is Ck0,Ck1, ...Ckm,

Then Cpq ... C1q,C0q is the binary representation of the number of bits equal to 1 among the q-th bit of {A[i],A[i+1], ... ,A[j-1]}.

The bit-level implementation (in python); all bits are managed in parallel.

def add(counter,x):
    k = 0
    while x :
        x, counter[k] = x & counter[k], x ^ counter[k]
        k += 1

def sub(counter,x):
    k = 0
    while x :
        x, counter[k] = x & ~counter[k], x ^ counter[k]
        k += 1

def val(counter,count):  # return A[i] & .... & A[j-1] if count = j-i.  
    k = 0
    res = -1
    while count:
       if count %2 > 0 : res &= counter[k]
       else: res &= ~counter[k]
       count //= 2
       k += 1
    return res

And the algorithm :

def solve(A,P):
    counter = np.zeros(32, np.int64) # up to 4Go
    n = A.size
    i = j = 0
    K=P # trig fill buffer
    mini = np.int64(2**63-1)

    while i<n :

        if  K<P or j == n :     # dump buffer 
            sub(counter,A[i])
            i += 1
        else:                   # fill buffer
            add(counter,A[j])
            j += 1

        if j>i: 
            K = val(counter, count)
            X = np.abs(K - P)
            if mini > X: mini = X
        else : K = P            # reset K     

    return mini

val,sub and add are O(ln N) so the whole process is O(N ln N)

Test :

n = 10**5
A = np.random.randint(0, 10**8, n, dtype=np.int64)
P = np.random.randint(0, 10**8, dtype=np.int64)

%time solve(A,P)
Wall time: 0.8 s
Out: 452613036735

A numba compiled version (decorate the 4 functions by @numba.jit) is 200x faster (5 ms).

这篇关于用目标按位与值查找子数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！