在 O(n) 或 O(n*log(n)) 中计算按位 "AND" 为 2 的幂的数组中无序对的数量

Question

如何计算按位 AND 是 2 的幂的数组中无序对的数量。例如，如果数组是 [10,7,2,8,3]。答案是6。说明（基于 0 的索引）：

a[0]&a[1] = 2
a[0]&a[2] = 2
a[0]&a[3] = 8
a[0]&a[4] = 2
a[1]&a[2] = 2
a[2]&a[4] = 2

我想到的唯一方法是蛮力。如何优化它以在 O(n) 或 O(n*log(n))?

中执行

数组大小的限制可以达到最大值 10^5。该数组中的值最多可达 10^12.

这是我尝试过的暴力破解代码。

    int ans = 0;
    for (int i = 0; i < a.length; i++) {
        for (int j = i + 1; j < a.length; j++) {
            long and = a[i] & a[j];
            if ((and & (and - 1)) == 0 && and != 0)
                ans++;
        }
    }
    System.out.println(ans);

Answer 1

将您的值数组转换为索引集数组，其中每个集对应于一个特定的位，并包含原始集合中具有该位集的值的索引。例如，您的示例数组 A = [10,7,2,8,3] 变为 B = [{1,4}, {0,1,2,4}, {1}, {0,3}]。一个固定大小的位向量数组是一个理想的数据结构，因为它使 set union/intersection/setminus 相对容易和高效。

一旦你有了集合 B 的数组（需要 O(nm) 时间，其中 m 是以位为单位的整数的大小），遍历每个元素 i 再次计算 A_j|B_j∖i∖⋃_kB_k:k≠j∧i∈B_k|:i∈B_j。将这些加在一起并除以 2，应该是对的数量（"divide by 2" 是因为这对每对计数两次，因为它计算的是数量每个数字配对的数字）。应该只采用 O(nm²) 假设您将 setminus 操作计为 O(1) - 如果您将它们计为 O(n)，那么您将回到 O(n ²), 但如果你有有效的位集，至少你的常数因子应该很小。

伪代码：

foreach A[i] in A:
    foreach bit in A[i]:
        B[bit] += {i}

pairs = 0
foreach A[i] in A:
    foreach B[j] in B:
        if i in B[j]:
            tmp = B[j] - {i}
            foreach B[k] in B:
                if k != j && i in B[k]:
                    tmp -= B[k]
            pairs += |tmp|

return pairs/2

Answer 2

尽管此答案适用于较小的范围限制（可能适合大约 2^20），但我想我会添加它，因为它可能会添加一些有用的信息。

我们可以调整 bit-subset dynamic programming idea 以获得具有 O(2^N * N^2 + n * N) 复杂度的解决方案，其中 N 是范围内的位数，n 是数字列表中的元素。（因此，如果整数限制为 [1, 1048576] 或 2^20，其中 n 为 100,000，我们将进行 2^20 * 20^2 + 100000*20 = 421,430,400 次迭代。）

我们的想法是，我们想要计算具有重叠位子集的实例，并添加一个固定的设置位。给定 Ai——为简单起见，取 6 = b110——如果我们要找到所有 AND 为零的伙伴，我们将取 Ai 的否定，

110 -> ~110 -> 001

现在我们可以构建一个采用递减掩码的动态程序，从完整数字开始，向左递减掩码

001
^^^

001
^^

001
^

Ai 取反的每个设置位代表一个零，可以将其与 1 或 0 进行“与”运算以达到相同的效果。 Ai 取反的每个未设置位代表 Ai 中的一个设置位，我们只想与零配对， 除了单个设置位 .

我们通过分别检查每种可能性来构造这个设置位。那么在哪里计算将 Ai 与 Ai 归零的对，我们会做类似

的事情

001 ->
  001
  000

我们现在要枚举

每次固定一位。

我们可以通过在内部迭代中添加一个维度来实现这一点。当掩码在末尾确实有一个设置位时，我们 "fix" 相关位通过只计算前一个 DP 单元的结果，而不是通常的子集联合可能有那个位设置与否。

这里有一些 JavaScript 代码，用于在最后与暴力解决方案进行比较来进行测试。

var debug = 0;

function bruteForce(a){
  let answer = 0;
  for (let i = 0; i < a.length; i++) {
    for (let j = i + 1; j < a.length; j++) {
      let and = a[i] & a[j];
      if ((and & (and - 1)) == 0 && and != 0){
        answer++;
        if (debug)
          console.log(a[i], a[j], a[i].toString(2), a[j].toString(2))
      }
    }
  }
  return answer;
}
  
function f(A, N){
  const n = A.length;
  const hash = {}; 
  const dp = new Array(1 << N);
  
  for (let i=0; i<1<<N; i++){
    dp[i] = new Array(N + 1);
    
    for (let j=0; j<N+1; j++)
      dp[i][j] = new Array(N + 1).fill(0);
  }
      
  for (let i=0; i<n; i++){
    if (hash.hasOwnProperty(A[i]))
      hash[A[i]] = hash[A[i]] + 1;
    else
      hash[A[i]] = 1;
  }
  
  for (let mask=0; mask<1<<N; mask++){
    // j is an index where we fix a 1
    for (let j=0; j<=N; j++){
      if (mask & 1){
        if (j == 0)
          dp[mask][j][0] = hash[mask] || 0;
        else
          dp[mask][j][0] = (hash[mask] || 0) + (hash[mask ^ 1] || 0);
        
      } else {
        dp[mask][j][0] = hash[mask] || 0;
      }
    
      for (let i=1; i<=N; i++){
        if (mask & (1 << i)){
          if (j == i)
            dp[mask][j][i] = dp[mask][j][i-1];
          else
            dp[mask][j][i] = dp[mask][j][i-1] + dp[mask ^ (1 << i)][j][i - 1];
          
        } else {
          dp[mask][j][i] = dp[mask][j][i-1];
        }
      }
    }
  } 
  
  let answer = 0; 
  
  for (let i=0; i<n; i++){
    for (let j=0; j<N; j++)
      if (A[i] & (1 << j))
        answer += dp[((1 << N) - 1) ^ A[i] | (1 << j)][j][N];
  }

  for (let i=0; i<N + 1; i++)
    if (hash[1 << i])
      answer = answer - hash[1 << i];

  return answer / 2;
} 
 
var As = [
  [5, 4, 1, 6], // 4
  [10, 7, 2, 8, 3], // 6
  [2, 3, 4, 5, 6, 7, 8, 9, 10],
  [1, 6, 7, 8, 9]
];

for (let A of As){
  console.log(JSON.stringify(A));
  console.log(`DP, brute force: ${ f(A, 4) }, ${ bruteForce(A) }`);
  console.log('');
}

var numTests = 1000;

for (let i=0; i<numTests; i++){
  const N = 6;
  const A = [];
  const n = 10;
  for (let j=0; j<n; j++){
    const num = Math.floor(Math.random() * (1 << N));
    A.push(num);
  }

  const fA = f(A, N);
  const brute = bruteForce(A);
  
  if (fA != brute){
    console.log('Mismatch:');
    console.log(A);
    console.log(fA, brute);
    console.log('');
  }
}

console.log("Done testing.");

在 O(n) 或 O(n*log(n)) 中计算按位 "AND" 为 2 的幂的数组中无序对的数量

Calculate the number of unordered pairs in an array whose bitwise "AND" is a power of 2 in O(n) or O(n*log(n))

algorithm

data-structures

bit-manipulation

bitmask