我的问题如下:我有一个值 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 的起始值,这是'没有太大的改进)。
编辑:同样重要的是,对于每个生成的值,都会生成很多额外的工作,这意味着很多重复项是不可能的(一些重复项,即使无法识别也可以,没有任何对已完成工作的副作用,这只是一种减速)。
最佳答案
这会以相反的顺序生成所有位模式(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;
}
关于c - 为给定掩码生成所有位模式,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14672013/