增加'蒙面'位集

Question

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

我正在查看屏蔽的位集,即位集,其中设置位是掩码的子集,即0000101使用掩码1010101.我想要完成的是增加位集,但仅限于屏蔽位.在这个例子中,结果将是0010000.为了使它更清晰一点,只提取掩码位,0011即将0100它们递增并再次分配给掩码位,给出0010000.

有没有人看到一种有效的方法来做到这一点,没有使用bitcans和前缀掩码的组合手动实现操作？

Answer 1

只需将非掩码位填充为1,以便它们传播进位:

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

因为他们接受了,因此可能对OP不重要,但也许应该注意,这将使非掩码位归零.如果他们在其他地方需要,你必须更加小心地替换`x`.可能是`x =(x&〜mask)| (((x | ~mask)+ 1)&mask);`. (22认同)
这是一个很好的伎俩...我说的几乎没有魔法没有:) (11认同)
@EugeneSh.永远不要相信它不是这样. (8认同)
@TripeHound如果不需要它们,即使使用位掩码也会有什么意义？ (2认同)

Answer 2

虽然与接受的答案相比并不直观,但这只需3个步骤:

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

然后它变得等同于接受的答案.

` - (x ^ mask)==〜((x ^ mask) - 1)==〜(x ^ mask)+ 1 ==(x ^ ~mask)+ 1 ==(x | ~mask)+ 1` .最后一个等式成立,因为位集是不相交的,其他位置始终为真(至少在2 - 补码中). (5认同)
也许值得指出的是,这些并没有优化相同,这通常与做点苦恼的人有关:https://godbolt.org/g/7VWXas - 虽然哪一个实际上更短似乎取决于编译器.不知道哪一个会*更快*或者差异是否显着. (5认同)
zch的答案非常直观,我可以立即看到它是正确的,因为他清楚的解释.这个答案的逻辑是什么？该配方如何发挥作用以达到预期效果？我很好奇发现的过程,这里的见解的本质. (2认同)

Answer 3

如果迭代的顺序不重要,并且减量操作将满足您的需求,则可以仅使用两个操作:

让我们开始吧

x = mask

并获得以前的价值

x = (x - 1) & mask

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