Efficient way to get all matching bitmasks?

Question

Lets say I have some patterns as 64 bits integers. Given a 64 integer n how to list all patterns matching n efficiently?

More precisely I am interested in this set: {p_i in patterns such as (n & p_i) == p_i}

Thanks for your help

Answer 1

One optimized solution not of O(log(P)) complexity, but better than O(P)

LSB => Least Significant Bit

Map each pattern to a set as

m[i] = { p for p in patterns if p's ith LSB is zero }

O(P) complexity

positions = Find all non-set bit positions of N i.e with zero value

O(1) complexity

Your answer would be intersection of { patterns, m[i] for i in positions}

The intersection of the k sorted set can be computed in O(N) where N is the largest set cardinality.

This will not work when all bits are set, more specifically when your input is 2^64-1. In this case all bits are set so you can't find any position with unset bit, in that case print all patterns.

---

Example:

p = {1,2,3,4,5,6,7 } <=> {b001, b010, b011, b100, b101, b110, b111}

pattern_map =

{
   1: [010, 100, 110],
   2: [001, 100, 101],
   3: [001, 010, 011],
   4: [0001, 0010, 0011, 0100, 0101, 0110, 0111]
}

• n = 1 <=> b001

  2nd and 3rd LSB are zero

  => intersection of [001, 010, 011, 100, 101, 110, 111], [001, 100, 101] and [001, 010, 011]

  => [001]

• n = 2 <=> b010

  1st and 3rd LSB are zero

  =>intersection of [001, 010, 011, 100, 101, 110, 111], [010, 100, 110] and [001, 010, 011]

  => [010]

• n = 3 <=> b011

  3rd LSB is zero

  => intersection of [001, 010, 011, 100, 101, 110, 111] and [001, 010, 011]

  => [001, 010, 011]

• n = 4 <=> b100

  1st and 2nd LSBs are zero

  => intersection of [001, 010, 011, 100, 101, 110, 111], [010, 100, 110] and [001, 100, 101]

  => [100]

• n = 5 <=> b101

  2nd LSB is zero

  => intersection of [001, 010, 011, 100, 101, 110, 111] and [001, 100, 101]

  => [001, 100, 101]

• n = 6 <=> b110

  1st LSB is zero

  =>intersection of [001, 010, 011, 100, 101, 110, 111] and [010, 100, 110]

  =>[010, 100, 110]

• n = 7 => b111

  4th LSB is zero

  => [0001, 0010, 0011, 0100, 0101, 0110, 0111]

Answer 2

The naive methods is to check all numbers, from 0 to 2^64-1 against the pattern n. You need 2^64 steps (in C++, have a look at vectorization to reduce the number of steps).

There is no method that gives you the same result in 64 steps (see below), but you can improve the naive method.

First idea: let's say your pattern is:

bit     0 0 ...  0 1 ? ? ? ? ? 1 0 ... 0
pos     0 1 ...    i  ...      j  ... 63

Where i is the first 1 and j the last 1. You can find i and j in 64 steps (check against 2^k where 0 <= k < 64).

Obviously, no number greater than or equal to 2^(i+1) will match the pattern, because you have a 1 before the position i. Hence you just have to check 2^(i+1) numbers.

Now, let's consider j: if a number p matches n, then all numbers matching the pattern have the form p + t.2^j, because:

• p + k where k < t.2^j has a 1 after the position j, and
• p + k where k > t.2^j have the form (euclidean division): (p + q.2^j) + r where r < 2^j. Again, if r != 0, you have a 1 after the position j. You recognized the step. You don't have to check every number, just one out of 2^j numbers.

Conclusion: you can check the numbers against the pattern in 64 + 2^(i-j+1) steps.

Second idea: you can try to generate all numbers, not just check. In theory, it may be be faster, but in practice, I don't think this will be efficient. Let's say the pattern is:

bit     0 ... 0 1   0 ... 1  ...  1   ... 1   0 ... 0
pos             p_1       p_2     p_3 ... p_k

Where the k 1s are at positions p_1, p_2, ..., p_k. 2^k numbers will match the pattern (this is why you can't have the solution in 64 steps): the numbers having 1 or 0 at the positions p_i and 0 elsewhere.

To generate those numbers, iterate over all numbers p between 0 and 2^(k-1). For each p:

• Start with N = 0.
• Check p against all 2^i, with i between 0 and k-1. If there is a match (a 1 at the position i), add 2^{p_i} to N.
• At the end, you have generated a number N that matches the pattern.

This will generate all the numbers matching the pattern in 2^k * k steps.

---

EDIT Some thoughts

• Whatever method you choose, 0 (64 bits) and n (the pattern itself) will match the pattern.
• First method: n, the pattern itself, is an upper bound to the matching numbers. Any number greater than n will have at least a 1 on a 0 of the pattern (think of the carry). This upper bound is finer than 2^{i+1}.
• First method: you can find i and j by bisection, in a lower number of steps than 64.
• It's possible to compute p_1 = i, p_2, ... p_k = j and to choose the most promising method. E.g. don't use the first method for ̀b1000000000000000000000000000000000000000000000000000000000000001.
• First method seems slower than second method, but it may take advantage of branch prediction.

Answer 3

Luckily your check (n & p1) == p1 is transitive. Therefore you can compute that relation on the pattern space too and use it to skip checks. I call this relation coverage and use the symbol ▷ as an abbreviation. p1 covers p2 iff all set bits in p2 are also set in p1. Formally:

p1 covers p2 iff p1 ▷ p2 iff (p1 & p2) == p2.

Transitivity means from n ▷ p1 and p1 ▷ p2 follows n ▷ p2. Therefore we can omit the check n ▷ p2 if we already know n ▷ p1. To use this as often as possible, we have to make sure that p1 is always checked before p2 because p1 ▷ p2. Computing this order is the first step:

P = { ... } // set of patterns

operator ▷(p1, p2):
  return (p1 & p2) == p2

function initCoverGraph():
   // dummy that covers everything
   root = 0xFFFFFFFFFFFFFFFF
   // max. set of root's covers such that no child covers another 
   root.children = {}
   for p in P:
     insertBelow(r, p)

function insertBelow(p1, p2):
   isChild = true
   for c in p1.children:
      if p2 ▷ c1:
         p1.children.remove(c)
         p2.children.add(c)
      if c ▷ p2:
         insertBelow(c, p2)
         isChild = false
         break
   if isChild:
      p1.children.add(p2)
     

You can optimize this further. From p1 ▷ p2 follows p1 > p2. To leverage this, use sorted sets for P and each .children then split insertBelow's loop in two, iterating only the relevant parts of p1.children.

Now we have built the directed acyclic graph (DAG) of the ▷-relation. For fast queries each node p1 also needs p1.successors, the transitive reflexive children of p1. That is, p1.successors = {p1} u p1.children u { c.children | c in p1.children } u .... You can compute this using a single DFS from the root node. For brevity we just assume we already did.

Now, lets do some queries.

function query(n, root, coveredByN={}):
    if coveredByN.contains(root):
      return
    for c in root.children:
      if n ▷ c:
        coveredByN.addAll(c.successors)
      else:
        query(n, c, coveredByN)

Note that query correctly ignores the dummy root. If P itself contains p1 = 0xFF...FF (equal to root, but not the same) then root.children contains p1, resulting in the correct result.

This should already be quite fast. If needed you can optimize this further by using sorted sets (as mentioned above) and appropriate data structures.

The actual performance heavily depends on the distribution of your patterns. In some cases it could be faster to approach the problem from the other side (from n !▷ p2 and p1 ▷ p2 follows n !▷ p1).

Answer 4

If I understand the problem correctly (would appreciate more details in question). You could use Numpy broadcasting with np.bitwise_and for your task.

EDIT: My solution is in python, I just realized, you have not mentioned a language tag.

import numpy as np

p = np.random.randint(0,5000,(1000,),dtype='int64') #5000 patterns
n = np.random.randint(0,10000,(500,),dtype='int64') #10000 integers

compare = np.bitwise_and(n[:,None],p[None,:]) == p[None,:] 
#True if (n & pi) == pi, else False

n_idx = 0 #For 0th n integer in my list
p_idx = np.argwhere(compare[0]).flatten() #This is the index of patterns that match
print('integer ->', n[0])
print('matching patterns ->',p[p_idx])

integer -> 9738
matching patterns -> [1538 1544 1026 1536 1536 1034  520]