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

Although this answer is for a smaller range constraint (possibly suited up to about 2^20), I thought I'd add it since it may add some useful information.

We can adapt the bit-subset dynamic programming idea to have a solution with O(2^N * N^2 + n * N) complexity, where N is the number of bits in the range, and n is the number of elements in the list. (So if the integers were restricted to [1, 1048576] or 2^20, with n at 100,000, we would have on the order of 2^20 * 20^2 + 100000*20 = 421,430,400 iterations.)

The idea is that we want to count instances for which we have overlapping bit subsets, with the twist of adding a fixed set bit. Given Ai -- for simplicity, take 6 = b110 -- if we were to find all partners that AND to zero, we'd take Ai's negation,

110 -> ~110 -> 001

Now we can build a dynamic program that takes a diminishing mask, starting with the full number and diminishing the mask towards the left

001
^^^

001
^^

001
^

Each set bit on the negation of Ai represents a zero, which can be ANDed with either 1 or 0 to the same effect. Each unset bit on the negation of Ai represents a set bit in Ai, which we'd like to pair only with zeros, except for a single set bit.

We construct this set bit by examining each possibility separately. So where to count pairs that would AND with Ai to zero, we'd do something like

001 ->
  001
  000

we now want to enumerate

011 ->
  011
  010

101 ->
  101
  100

fixing a single bit each time.

We can achieve this by adding a dimension to the inner iteration. When the mask does have a set bit at the end, we "fix" the relevant bit by counting only the result for the previous DP cell that would have the bit set, and not the usual union of subsets that could either have that bit set or not.

Here is some JavaScript code to demonstrate with testing at the end comparing to the brute-force solution.

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.");

Answer 2

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