英文:
Enumerating intersections of two sequences
问题
I have two sequences:
- 一个无符号64位数
k的倍数，例如k=5：{0, 5, 10, 15, 20, 25, ...} - 64位掩码
m的子集，加上64位常数C，例如m=0b1011：{C+0, C+1, C+2, C+3, C+8, C+9, C+10, C+11}。注意：C与m不重叠，即(m & C) = 0。
除了逐个检查 k 的每个倍数并检查是否符合第二个序列的条件，或者检查掩码 m 的每个子集并与 C 进行 OR 运算，然后检查是否能被 k 整除之外，还有其他方法可以列举这两个序列的交集吗？
64位数 P 在这两个序列的交集中，如果 P % k == 0 并且 (P & C) == C 并且 (P & ~(C | m)) = 0。
注意：实际上很容易枚举第二个序列：
uint64_t m = ...; uint64_t 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);
编辑：枚举的顺序无关紧要。
此外：我不一定希望枚举它们全部，但我想要一种迭代器，可以始终推进并获取下一个交集。
英文:
I have two sequences:
- Multiples of an unsigned 64-bit number
k, example fork=5:{0, 5, 10, 15, 20, 25, ...} - Subsets of the 64-bit mask
mplus 64-bit constantC, example form=0b1011:{C+0, C+1, C+2, C+3, C+8, C+9, C+10, C+11}. Note:Cis disjoint fromm, 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
答案1
得分: 1
C mod k 是一个常数，表示我们正在寻找满足对于模 k 而言其结果为特定值的 m 的子集 — 即当其与 C mod k 相加后结果为零模 k 的子集。
x = (k - (C mod k)) mod k
m 中的每个比特作为 2 的幂对于模 k 也是常数。因此，任务似乎是枚举那些总和为 x 模 k 的组合。
例如，对于已见过的组合，可以通过将当前在 m 中的幂对 k 取模来生成新的组合。一个即时的优化可能是将在 m 中与 k 对模相等的幂进行分组。除此之外，我不知道有什么技巧可以加速这种搜索 —— 对于模 k 的组合状态数量可能取决于 k 和 m 两者。
英文:
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.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论