8

我的问题如下：我有一个值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 的起始值，这不是一种提升）。

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

4

3 回答 3

16

这会以相反的顺序生成所有位模式（的初始值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;
}
于 2013-02-03T11:49:14.917 回答
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 代码应该不难 - 替换为bitString和int或类似。[pos]& 1 << pos

于 2013-02-03T11:41:47.170 回答
0

最理想的方式是这样的：

  1. 计算掩码中设置的位数，p
  2. 找出一种将“标准化”二进制值中的位打乱到由模式决定的位置的方法
  3. 数到 0..2 p -1
  4. 对于每个值 shuffle 以生成模式兼容的值

这当然假设进行改组是相当有效的，否则更容易通过根据模式中的总位数从 0 计数到最大可能值并在每次计数时应用模式来强制它。不过，检测重复项可能有点贵。

对于p = 9(binary 1001 2 )，只设置了两个位，因此我们知道要生成 2 2 = 4 个值。

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

  • 位 0 是从位 0 复制的
  • 位 3 是从位 1 复制的

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

  • 00 2给出输出 0000 2
  • 01 2给出输出 0001 2
  • 10 2给出输出 1000 2
  • 11 2给出输出 1001 2
于 2013-02-03T11:39:39.257 回答