计算一个数组的无序对的数量，按位“ 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);

如何计算按位与为2的幂的数组中无序对的数量。例如，如果数组为[10,7,2,8,3]。答案是6。说明（从0开始的索引）：a [0]＆a [1] = 2 a [0]＆...

Answer 1

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

Answer 2

我们可以使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迭代的数量级。）