增加“蒙面”的位集

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

我正在查看掩码的位集，即设置位是掩码子集的位集，即带掩码1010101 。 我想要完成的是增加位集，但只有掩码位。 在这个例子中，结果是0010000 。 为了使其更清楚一点，只提取掩码位，即0011 ，将它们递增到0100并再次将它们分配给掩码位，得到0010000 。

有没有人看到一个有效的方法来做到这一点，而不是手动使用bitscans和前缀掩码的组合执行操作？

Answer 1

只需填充非掩码位，以便传播进位：

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

Answer 2

虽然与被接受的答案相比并不直观，但这只有三个步骤：

 x = -(x ^ mask) & mask; 

这可以通过zchbuild议来validation：

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

然后它变成相当于被接受的答案。

Answer 3

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

我们开始吧

x = mask

并获得以前的价值

x = (x - 1) & mask

x - 1部分将最后一个非零位更改为零，并将所有不重要的位设置为1。 然后& mask部分只留下掩码位。