递增“掩码”位集

Question

我目前正在编写一种树形枚举器，在其中遇到了以下问题：

我正在研究掩码位集，即只有在掩码内的位才是置位的位集，例如用掩码 1010101 来描述 0000101。我想要实现的是递增位集，但仅限于掩码内的位。在这个例子中，结果将会是 0010000。为了更清晰地表达，仅提取掩码内的位，即 0011，将其递增至 0100 并再次分布到掩码内的位，得到 0010000。

有没有人知道一种高效的方法来做到这一点，而不是手动使用位扫描和前缀掩码的组合来实现操作？

- Tobias Ribizel

Answer 1

将非掩码位填充为1，以便它们传递进位：

// increments x on bits belonging to mask
x = ((x | ~mask) + 1) & mask;

- zch

---

这是个不错的技巧...几乎就像我之前所说的魔法不存在 :) - Eugene Sh.

@EugeneSh. 别相信这不是真的。 - zch

OP可能不认为这很重要，因为他们已经接受了，但是可能值得注意的是，这将使非掩码位变为零。如果这些位在其他地方被需要，你在替换“x”时必须更加小心。可能的替代方式是 x = (x & ~mask) | (((x | ~mask) + 1) & mask);。 - TripeHound

@TripeHound 如果它们不需要，那么使用位掩码的意义是什么？ - someonewithpc

@someonewithpc 不确定你想说/问什么。我不知道为什么 OP 需要增加一组非相邻的位，所以我不知道原始值中的其他位是否重要。例如，如果原始值是 0101101（例如在非掩码位中为 .1.1.0.，在“计数器”中为 0.0.1.1），他们是否需要 0111000（一个新的“计数器”为 0.1.0.0，同时保留 .1.1.0.）或者只有 0010000 是可以接受的。这个答案（可能还有其他答案，但我没有检查）给出了后者；如果需要前者，我的版本应该给出前者。 - TripeHound

Answer 2

虽然与被接受的答案相比不太直观，但这种方法仅需要三个步骤：

x = -(x ^ mask) & mask;

可以按照zch的建议进行验证：

  -(x ^ mask)
= ~(x ^ mask) + 1  // assuming 2's complement
= (x ^ ~mask) + 1
= (x | ~mask) + 1  // since x and ~mask have disjoint set bits

那么它就等同于被接受的答案。

- nglee

---

zch的答案非常直观，他的清晰解释让我立刻看出它是正确的。这个答案的逻辑是什么？这个公式是如何产生所需效果的？我对发现的过程、洞察力的本质很好奇。 - FooF

如果您证明了只要x是mask的子集，就有-(x ^ mask) == (x | ~mask) + 1，那么我认为您的验证会简单得多，然后可以参考我的答案。 - zch

-(x^mask) == ~((x ^ mask) - 1) == ~(x ^ mask) + 1 == (x ^ ~mask) + 1 == (x | ~mask) + 1。最后一个等式成立是因为位集是不相交的，其他等式总是成立（至少在二进制补码中）。 - zch

对于那些好奇我采取了哪些步骤来得出这个答案的人，可以参考这个页面。 - nglee

也许值得指出的是，它们的优化方式不同，这常常与进行位操作的人有关：https://godbolt.org/g/7VWXas - 尽管哪个更短似乎取决于编译器。不知道哪个更快，或者差异是否显著。 - Alex Celeste

Answer 3

如果迭代顺序不重要且递减操作能够满足您的需求，则可以仅使用两个操作：

首先执行

x = mask

然后通过以下方式获取上一个值

x = (x - 1) & mask

x - 1 部分将最后一个非零位更改为零，并将所有低位设置为1。然后 & mask 部分只保留其中的掩码位。

- DAle

---

2个操作，不错。然而我认为这是相同的方法，只是通过零来传递借位，而不是通过1来传递进位。 - zch

@zch，没错，谢谢。我会重新表述答案。 - DAle

只有当 x 的所有非掩码位都清零时，才能起作用。 - Jasen

@Jasen，好的。但是设置那些非掩码位并不困难。其他答案也有类似的问题。 - DAle