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

Question

如何计算按位 的数组中无序对的数量和 是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

虽然这个答案是针对较小的范围约束(可能适合大约 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 -- 如果我们要找到所有与为零的合作伙伴，我们将采用 Ai的否定，

110 -> ~110 -> 001

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

001
^^^

001
^^

001
^

对 Ai 取反的每个设置位表示一个零，它可以与 1 或 0 进行 AND 运算以达到相同的效果。 Ai 的否定上的每个未设置位表示 Ai 中的一个设置位，我们只想与零配对，除了单个设置位。

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

001 ->
  001
  000

我们现在要枚举

011 ->
  011
  010

101 ->
  101
  100

每次修复一个位。

我们可以通过向内部迭代添加维度来实现这一点。当掩码在末尾确实有一个设置位时，我们通过仅计算将设置该位的前一个 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.");