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))

Question

How to calculate number of unordered pairs in an array whose bitwise AND is a power of 2. For ex if the array is [10,7,2,8,3]. The answer is 6. Explanation(0-based index):

• 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

The only approach that comes to my mind is brute force. How to optimize it to perform in O(n) or O(n*log(n))?

The constraints on the size of array can be at max 10^5. And the value in that array can be upto 10^12.

Here is the brute force code that I tried.

    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

Transform your array of values into an array of index sets, where each set corresponds to a particular bit and contains the indexes of the value from the original set that have the bit set. For example, your example array A = [10,7,2,8,3] becomes B = [{1,4}, {0,1,2,4}, {1}, {0,3}]. A fixed-sized array of bitvectors is an ideal data structure for this, as it makes set union/intersection/setminus relatively easy and efficient.

Once you have that array of sets B (takes O(nm) time where m is the size of your integers in bits), iterate over every element i of A again, computing ?_j|B_j∖i∖⋃_kB_k:k?j?i∈B_k|:i∈B_j. Add those all together and divide by 2, and that should be the number of pairs (the "divide by 2" is because this counts each pair twice, as what it is counting is the number of numbers each number pairs with). Should only take O(nm²) assuming you count the setminus operations as O(1) -- if you count them as O(n), then you're back to O(n²), but at least your constant factor should be small if you have efficient bitsets.

Pseudocode:

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