计算按位“ AND”为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））中执行？

对数组大小的限制最大为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}, {0,3}, {0}]。为此，固定大小的位向量数组是一种理想的数据结构，因为它使集合并集/交集/集合减相对容易和有效。

一旦有了集合B的数组（花费O（nm ²）时间，其中m是整数的大小，以位为单位），再次遍历A的每个元素i，计算∑ _j popcount（B _j＆setminus; i＆setminus;＆bigcup; _k≠j B _k）。将它们全部相加并除以2，然后应该为对数。假设您将setminus运算计为O（1），则应该仅取O（nm ²）－如果将其计为O（n），则返回O（n ²） ，但是如果您有有效的位集，那么至少您的常数因子应该很小。