c - 使用按位运算符的集合中的下一组 n 个元素

Question

阅读《C - 参考手册（第五版）》一书，我偶然发现了这段代码（SET 中的每个整数都由一个位位置表示）：

typedef unsigned int SET;

#define emptyset ((SET) 0)

#define first_set_of_n_elements(n) (SET)((1<<(n))-1)

/* next_set_of_n_elements(s): Given a set of n elements,
   produce a new set of n elements. If you start with the
   result of first_set_of_n_elements(k)/ and then at each
   step apply next_set_of_n_elements to the previous result,
   and keep going until a set is obtained containing m as a
   member, you will have obtained a set representing all
   possible ways of choosing k things from m things. */
SET next_set_of_n_elements(SET x) {
    /* This code exploits many unusual properties of unsigned arithmetic. As an illustration:
      if x == 001011001111000, then
      smallest       == 000000000001000
      ripple         == 001011010000000
      new_smallest   == 000000010000000
      ones           == 000000000000111
      returned value == 001011010000111
    The overall idea is that you find the rightmost
    contiguous group of 1-bits. Of that group, you slide the
    leftmost 1-bit to the left one place, and slide all the
    others back to the extreme right.
    (This code was adapted from HAKMEM.) */

    SET smallest, ripple, new_smallest, ones;
    if (x == emptyset) return x;
    smallest     = (x & -x);
    ripple       = x + smallest;
    new_smallest = (ripple & -ripple);
    ones         = ((new_smallest / smallest) >> 1) -1;
    return (ripple | ones);
}

我迷失在“一”的计算中，这在计算中很重要。虽然我可以理解数学上的计算，但我不明白为什么会这样，或者如何。

在相关的说明中，该书的作者声称 first_set_of_n_elements 的计算“利用了无符号减法的属性”。(2^n)-1 如何是“利用”？

score 2 · Accepted Answer

首先，这段代码比较晦涩，看起来不值得花时间思考，只会产生无用的知识。

“利用”是代码依赖于各种算术规则的实现定义的行为。

001 0110 0111 1000 是一个 15 位的数字。为什么作者使用 15 位数而不是 16，我不知道。即使在 5 个版本之后，似乎仍然存在拼写错误。

如果我们在二进制补码系统上的二进制数前面加上一个减号（此处解释二进制补码），它将变成1110 1001 1000 1000。因为编译器将保留数字 (5752) 的十进制表示并将其转换为负等值 (-5752)。（但是，实际的数据类型将保持不变unsigned int，因此如果您尝试打印它，您将得到垃圾编号 59784。）

    0001 0110 0111 1000  
AND 1110 1001 1000 1000
  = 0000 0000 0000 1000

C 标准不强制执行二进制补码，因此该书中的代码不可移植。

score 2 · Accepted Answer

最小的计算得到你的 int 的第一个非 0 位。它是如何工作的？
让n是您的 int 的位长。与数字x（位b _n-1 ...b ₀）相反的计算方式是，当您将x与-x相加时，您将得到 2 ⁿ。由于您的整数只有 n 位长，因此会丢弃结果位并获得 0。
现在，让b' _n-1 ...b' ₀成为-x的二进制表示。
因为x +( -x ) 必须等于 2 ⁿ，当您遇到x的第一位 1 时（例如在位置i），相关的-x位也将设置为 1，并且在添加数字时，您将得到一个进位。
要获得 2 ⁿ，此进位必须传播到所有位，直到 int 的位序列结束。因此，在i < j < n的每个位置j处的-x位遵循以下属性：

b _j + b' _j + 1 = 10 _{（二进制）}

然后，从上面我们可以推断出： b _j = NOT(b' _j ) 因此， b _j & b' _j = 0

另一方面，-x的位 b' _j位于位置j使得0 <= j < i由以下规则决定：

b _j + b' _j = 0 或 10

由于所有相关的 b _j都设置为 0，因此唯一的选择是 b' _j = 0

因此，在x和-x中唯一为 1 的位是位置i

在您的示例中：

x = 001011001111000
-x = 110100110001000

因此，

0.0.1.0.1.1.0.0.1.1.1.1.0.0.0
1.1.0.1.0.0.1.1.0.0.0.1.0.0.0 AND
\================= ===/
0.0.0.0.0.0.0.0.0.0.1.0.0.0

然后，纹波将位置i（包括第 i 位）之后的每个连续“1”变为 0，并将紧随其后的第一个 0 位变为 1（由于进位传播）。这就是为什么你涟漪是：

r(x) = 0.0.1.0.1.1.0.1.0.0.0.0.0.0.0

一个被计算为最小（r（x））除以最小（x）。由于 minimum(x) 是一个整数，在位置i处只有一个位设置为 1 ，因此您有：

(最小(r(x)) / 最小(x)) >> 1 = 最小(r(x)) >>( i +1)

得到的整数也只有一位设置为 1，例如索引p，因此，减去 -1 到这个值将得到一个整数，这样：

对于每个j使得 0 <= j < p，
一个_j = 1
对于每个j这样p <= j < n，
一个_j = 0

最后，返回值是这样的整数：

参数的 1 位的第一个子序列设置为 0。
子序列之前的所有 0 位都设置为 1。
子序列后的第一个 0 位设置为 1。
其余位保持不变

然后，我无法解释剩下的部分，因为我不明白这句话：

获得一个包含 m 作为成员的集合

score 1 · Accepted Answer

这有点误导，因为它实际上利用了 2 的补码。首先，计算smallest：

在 2 的补码表示中，x注释中的-x是110100110001000。专注于其中最不重要的位x是一个；由于二进制补码本质上是 1 的补码加 1，因此该位将在两者中设置，x并且-x在它之后（在通往 LSB 的路上）没有其他位位置将具有该属性。这就是您获得最小位集的方式。

ripple非常简单，之所以这样命名，是因为它将 1 传播到 MSB，并smallest_ripple遵循上面的描述。

ones是我们应该添加到波纹中以便继续选择n元素的数字，如下图所示：

ones: 11  next set: 100011
ones:  1  next set: 100101
ones:  0  next set: 100110

运行它确实会向您展示从项目中选择n位的所有方法（需要位，因为n 位数需要最坏的 n+1 位来表示）。CHAR_BIT * sizeof(int) - 1CHAR_BIT * sizeof(int)-x

score 1 · Accepted Answer

首先，这里是我们可以在 n=4 时获得的输出示例。我们的想法是，我们从将“n”LSB 设置为“1”开始，然后遍历所有具有相同位数设置为“1”的数字组合：

它的工作方式如下。我将使用上面带有星号的数字作为示例：

正如其他答案中明确解释的那样，我们将 LSB 设置为“1”。
```
  101110
& 010011
= 000010 
```
我们通过将 LSB 添加到原始数字将其“移动”到左侧一位。如果紧靠左边的位是'0'，这很容易理解，因为后面的操作什么都不做。如果这个左边的位是'1'，我们得到一个将传播到左边的进位。最后一种情况的问题是'1'的数字会改变，所以我们必须回退一些'1'来保持它们的计数不变。
```
  101110
+ 000010 
= 110000
```
为此，我们检索新结果的 LSB，并通过将其与前一个 LSB 相除，我们得到进位传播的位数。这将在带有“-1”的最低位置转换为普通的“1”，
```
  010000
/ 000010
= 001000
>>     1 
-      1
= 000011
```
我们最终 OR 加法和加法的结果。
```
110011
```

score 0 · Accepted Answer

0

我会说“利用”是在操作（x & -x）中的符号无符号变化。

于 2013-01-31T09:57:09.127 回答

c - 使用按位运算符的集合中的下一组 n 个元素

5 回答 5

Related

Reference