c - 为给定掩码生成所有位模式

Question

我的问题如下:我有一个值 x 和一个模式 p 两个相同大小的变量。目标是遍历 x 的所有未被 p 屏蔽的位模式。

例子:如果我们有 p = 1001，我们想要找到 0000、0001、1000 和 1001 - 不一定按此顺序。

C99 中的标准实现(返回值指定我们是否已经返回了所有值):

static bool next(size_t val, size_t mask, size_t *out) {
    if (val == mask) {
        return false;
    }
    size_t current = val & mask;
    size_t inc = 1;
    size_t new_val = current + inc;
    while ((new_val & mask) <= current) {
        inc++;
        new_val = current + inc;
    }
    *out = new_val;
    return true;
}

我认为应该有一些技巧可以提高效率，但我似乎找不到任何大的改进(除了计算掩码的尾随零和适当设置 inc 的起始值，这是'没有太大的改进)。

编辑:同样重要的是，对于每个生成的值，都会生成很多额外的工作，这意味着很多重复项是不可能的(一些重复项，即使无法识别也可以，没有任何对已完成工作的副作用，这只是一种减速)。

Answer 1

这会以相反的顺序生成所有位模式(val 的初始值应等于 mask):

static bool next(size_t val, size_t mask, size_t *out) {
    if (val == 0) {
        return false;
    }

    *out = (val - 1) & mask;
    return true;
}

---

这(稍微不太明显的代码)按直接顺序生成所有位模式(val 的初始值应为零):

static bool next(size_t val, size_t mask, size_t *out) {
    if (val == mask) {
        return false;
    }

    *out = (val - mask) & mask;
    return true;
}