计算按位“与”是 O(n) 或 O(n*log(n)) 中 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)) 中执行？

对数组大小的限制可以是 max 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），但我想我应该添加它，因为它可能会添加一些有用的信息。

我们可以采用位子集动态规划思想来获得复杂的解决方案O(2^N * N^2 + n * N)，其中N是范围中的位数，n是列表中的元素数。（因此，如果整数限制为 [1, 1048576] 或 2^20，在n100,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，我们只想与零配对。

我们通过分别检查每种可能性来构造这个集合位。那么在哪里计算 ANDAi为零的对，我们会做类似的事情

001 ->
  001
  000

我们现在要枚举

011 ->
  011
  010

101 ->
  101
  100

每次修复一位。

我们可以通过向内部迭代添加一个维度来实现这一点。当掩码末尾确实有一个设置位时，我们通过仅计算具有该位设置的前一个 DP 单元的结果来“修复”相关位，而不是可能具有该位设置的子集的通常并集或不。

下面是一些 JavaScript 代码，用于演示最后的测试与暴力解决方案的比较。

110 -> ~110 -> 001