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

Question

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

8

我的问题如下：我有一个值 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的起始值，但这并不是很大的改进）。

编辑：还要注意的是，对于每个生成的值，都会产生大量额外的工作，这意味着许多重复是不可行的（一些重复，即使无法识别，也可以接受，没有任何副作用，只是减速）。

- Voo

用 p 适当地进行掩码处理，生成所有二进制数有什么问题？ - user529758

@H2CO3 啊，我应该提到给定数字的工作是相当昂贵的，因此生成大量重复数据是不可接受的。我会更新帖子以包括这一部分 - 忽略如此重要的因素是我的疏忽。否则，在我看来，所提出的方法在处理工作方面与当前方法是等效的。 - Voo

如果设定的位数很少，考虑到 size_t 可能是 64 位，那将非常低效。 - Paolo

3个回答

1

从您的示例中看，似乎这个伪代码可以解决问题：

current = p // set up current
getNotMasked(p, 0) // initial call


bitString current

getNotMasked(int pos)
  if (pos == current.length)
    print(current)
    return
  if (current[pos] == 1)
    current[pos] = 0
    getNotMasked(pos+1)
    current[pos] = 1
    getNotMasked(pos+1)
  else
    getNotMasked(pos+1)

从这里生成C代码不应该很难 - 用int替换bitString，用& 1 << pos或类似的内容替换[pos]即可。

- Bernhard Barker

0

最优的方式感觉如下：

计算掩码中设置位的数量，p
找出一种方法，将“标准化”的二进制值中的位洗牌到模式决定的位置
计数从0到2^p-1
对于每个值进行洗牌以生成与模式兼容的值

当然，这假设进行洗牌是相当高效的，否则更容易通过从0到取决于模式中总位数的最大可能值进行计数，并在每次计数时应用模式来暴力解决。检测重复项可能有点昂贵。

对于 p = 9（二进制1001₂），只有两个位被设置，因此我们知道有2² = 4个值要生成。

从右侧扫描1位的模式，我们可以形成以下“洗牌表”：

位0从位0复制
位3从位1复制

因此，我们可以从0到3进行计数，并根据表格对每个值进行重新排列：

00₂ 输出0000₂
01₂ 输出0001₂
10₂ 输出1000₂
11₂ 输出1001₂

- unwind

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Evgeny Kluev · Accepted Answer

这会以相反的顺序生成所有位模式（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;
}