生成给定掩码的所有位模式

Question

我的问题如下:我有一个值x和一个模式p两个相同大小的变量.目标是迭代未被 p掩盖的x的所有位模式.

例如:如果我们有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;
}