Optimal solution for "Bitwise AND" problem in C#

Question

Problem statement: Given an array of non-negative integers, count the number of unordered pairs of array elements, such that their bitwise AND is a power of 2.

Example: arr = [10, 7, 2, 8, 3]

Answer: 6 (10&7, 10&2, 10&8, 10&3, 7&2, 2&3)

Constraints:

1 <= arr.Count <= 2*10^5
0 <= arr[i] <= 2^12

Here's my brute-force solution that I've come up with:

    private static Dictionary<int, bool> _dictionary = new Dictionary<int, bool>();

    public static long CountPairs(List<int> arr)
    {
        long result = 0;

        for (var i = 0; i < arr.Count - 1; ++i)
        {
            for (var j = i + 1; j < arr.Count; ++j)
            {
                if (IsPowerOfTwo(arr[i] & arr[j])) ++result;
            }
        }

        return result;
    }

    public static bool IsPowerOfTwo(int number)
    {
        if (_dictionary.TryGetValue(number, out bool value)) return value;
        var result = (number != 0) && ((number & (number - 1)) == 0);
        _dictionary[number] = result;
        return result;
    }

For small inputs this works fine, but for big inputs this works slow. My question is: what is the optimal (or at least more optimal) solution for the problem? Please provide a graceful solution in C#. 😊

Answer 1

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, 4096] or 2^12, with n at 100,000, we would have on the order of 2^12 * 12^2 + 100000*12 = 1,789,824 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 (sorry, I do not know C#) 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 = [
  [10, 7, 2, 8, 3] // 6
];

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

One way to accelerate your approach is to compute the histogram of your data values before counting.

This will reduce the number of computations for long arrays because there are fewer options for value (4096) than the length of your array (200000).

Be careful when counting bins that are powers of 2 to make sure you do not overcount the number of pairs by including cases when you are comparing a number with itself.

Answer 3

int[] numbers = new[] { 10, 7, 2, 8, 3 };

static bool IsPowerOfTwo(int n) => (n != 0) && ((n & (n - 1)) == 0);

long result = numbers.AsParallel()
    .Select((a, i) => numbers
        .Skip(i + 1)
        .Select(b => a & b)
        .Count(IsPowerOfTwo))
    .Sum();

If I understand the problem correctly, this should work and should be faster.

• First, for each number in the array we grab all elements in the array after it to get a collection of numbers to pair with.
• Then we transform each pair number with a bitwise AND, then counting the number that satisfy our 'IsPowerOfTwo;' predicate (implementation here).
• Finally we simply get the sum of all the counts - our output from this case is 6.

I think this should be more performant than your dictionary based solution - it avoids having to perform a lookup each time you wish to check power of 2.

I think also given the numerical constraints of your inputs it is fine to use int data types.