如何高效遍历64位掩码M中可被整数P整除的所有子集？

以4位数字1101为例，它的所有子集为0000、0001、0100、0101、1000、1001、1100、1011，其中能被2整除的子集是0000、0100、1000、1100。

给定64位掩码M和64位整数P，如何遍历M的所有可被P整除的子集？

基础掩码子集遍历代码 #

遍历掩码的所有子集可采用如下C代码：

uint64_t superset = ...;
uint64_t subset = 0;
do {
    print(subset);
    subset = (subset - superset) & superset;
} while (subset != 0);

特殊场景下的优化策略 #

• 当M为~0（全1掩码）时，无需遍历所有子集，直接从0开始不断累加P，即可遍历所有符合条件的P的倍数。
• 当P是2的幂时，可通过M &= ~(P - 1)剔除无法使子集被P整除的低位，再遍历处理后的掩码的子集，所有结果自然满足整除要求。

通用场景的优化疑问 #

若不存在上述两种特殊约束，是否有比逐个检查每个子集是否能被P整除更优的方法？
朴素算法平均需要O(P)操作才能找到下一个符合条件的子集，能否实现优于O(P)的时间复杂度？

内容的提问来源于stack exchange，提问作者Null