Enumerating intersections of two sequences

Question

I have two sequences:

1. Multiples of an unsigned 64-bit number k, example for k=5: {0, 5, 10, 15, 20, 25, ...}
2. Subsets of the 64-bit mask m plus 64-bit constant C, example for m=0b1011: {C+0, C+1, C+2, C+3, C+8, C+9, C+10, C+11}. Note: C is disjoint from m, aka (m & C) = 0.

Aside from checking each and every multiple of k and checking if it matches the second sequence criteria, or checking every subset of the mask m and ORing with C and checking for division with k, are there any other ways I can enumerate all the intersection of those two sequences?

A 64-bit number P is in the intersection of those two sequences if P % k == 0 and (P & C) == C and (P & ~(C | m)) = 0.

Note: Enumerating over the second sequence is actually really easy:

uint64_t m = ..., C = ...;
uint64_t subset = 0;
do {
    uint64_t value = subset + C;
    print(value);
    // if (value % 5)   => in the intersection of the sequences
    subset = (subset - m) & m;
} while (subset != 0);

Edit: The order of enumeration doesn't matter

Also: I don't exactly hope to enumerate them all, but I want to have some sort of iterator which I can always advance and get the next intersection

Answer 1

C mod k is a constant that means we are looking for subsets of m that achieve one and only one value mod k — the one that when added to C mod k is zero mod k.

x = (k - (C mod k)) mod k

Each of the bits of m as a power of 2 is also constant mod k. So the task seems to be enumerating those combinations that sum to x mod k.

For example, for each of seen combinations, generate a new one by adding the current power of 2 in m mod k. One immediate optimisation could be to group the powers of 2 in m that are equal mod k. Other than that, I don't know of a trick to speed that kind of search up -- the number of combination states mod k could depend on both k and m.