bit-manipulation - 如何工作搜索 sebset 算法

Question

当我学习解决问题时，我遇到了一个怪物

int b = 0;
int x = (1<<6)|(1<<5)|(1<<2)
do {
// process subset
} while((b=(b-x)&x));

我知道结果，但我无法理解这段代码。

“(bx)&b”是什么意思？

你是怎么做的？

标签： bit-manipulationsubset

Answer 1

这是增加整数但仅使用位的子集的技巧，即x.

“(bx)&b”是什么意思？

这是错误的，它是(b - x) & x。

这个技巧的关键是减法，因此请确保您了解减法的作用。例如，考虑它的一种方法是，从 lsb 到 msb，从被减数的第 i 位减去减数的第 i 位和最后一次迭代的借位，得到第 i 位差额和下一次借。

x和b的形式b只能设置也设置在 中x的位，这在开始时是正确的，并且由于& x.

给出这些形式，x然后b我们知道每当产生借位时，它“向上流动”通过位，至少直到下一个设置位的位置（在原点之间x不能有设置位）b借用和那里，因为只有在设置了 inb时才能设置 bit in x）。因此，借位将一直到应该受到影响的下一位，并“跳过”其间所有额外的零。

借来的额外零也通过减法变成一，但& x又将所有这些变成零。

另一种写这个的方法，可能更容易考虑，是((b | ~x) + 1) & x. 原理相同，但有补充：“要忽略的位”由 设置| ~x，然后+1可以在必要时通过“间隙”。这种方法需要额外的操作，因为它需要用 1 而不是用 0 填充间隙，基于减法的技巧直接适用于所需的格式。