c++ - 创建一个按位集排序的序列

Question

我正在寻找可逆函数 unsigned f(unsigned) f(i) 中设置的位数随着 i 增加，或者至少不会减少。显然，f(0)那么必须为 0，并且 f(~0) 必须排在最后。两者之间有更大的灵 active 。 f(0) 之后，接下来的 32* 个值必须是 1U<<0至 1U<<31 ，但我不太关心顺序(它们都设置了 1 位)。

我想要一个不需要计算 f(0)...f(i-1) 的算法为了计算f(i) ，完整的表格也是行不通的。

这类似于格雷码，但我看不到重用该算法的方法。我试图用它来标记一个大数据集，并确定我搜索它们的顺序的优先级。我的想法是我有一把 key C ，然后我会检查标签 C ^ f(i) . i 的低值应该给我类似于 C 的标签，即只有几位不同。

[*] 不假设 unsigned 的奖励积分有 32 位。

[例子]一个有效的初始序列:

0, 1, 2, 4, 16, 8 ... // 16 and 8 both have one bit set, so they compare equal

无效的初始序列:

0, 1, 2, 3, 4 ... // 3 has two bits set, so it cannot precede 4 or 2147483648.

Answer 1

好吧，看来我有一个合理的答案。首先让我们定义 binom(n,k)作为我们可以设置 k 的方式的数量来自 n位。这是经典的帕斯卡三角形:

1  1
1  2  1
1  3  3  1
1  4  6  4  1
1  5 10 10  5  1
1  6 15 20 15  6  1
1  7 21 35 35 21  7  1
1  8 28 56 70 56 28  8  1
...

易于计算和缓存。注意每一行的总和是1<<lineNumber .

接下来我们需要的是 partial_sum那个三角形的:

1  2
1  3  4
1  4  7  8
1  5 11 15 16
1  6 16 26 31  32
1  7 22 42 57  63  64
1  8 29 64 99  120 127 128
1  9 37 93 163 219 247 255 256 
...

同样，可以通过将前一行的两个值相加来创建此表，除了现在每行的新条目是 1<<line。而不是 1 .

让我们使用上面的这些表来构建f(x)对于 8 位数字(它可以简单地概括为任意数量的位)。 f(0)仍然必须为 0。查看第一个三角形的第 8 行，我们看到接下来的 8 个条目是 f(1)至 f(9) , 都设置了一位。接下来的 28 个条目 (7+6+5+4+3+2+1) 都设置了 2 位，即 f(10) 到 f(37)。接下来的 56 个条目，f(38) 到 f(93) 有 3 个位，并且有 70 个条目设置了 4 个位。从对称性我们可以看出它们以 f(128) 为中心，特别是 f(94) 到 f(163)。很明显，唯一一个设置了 8 位的数字排在最后，如 f(255)。

因此，通过这些表格，我们可以快速确定必须在 f(i) 中设置多少位。只需在表的最后一行进行二进制搜索。但这并不能准确回答设置了哪些位。为此，我们需要前面的行。

表中的每个值都可以从上一行创建的原因很简单。 binom(n,k) == binom(k, n-1) + binom(k-1, n-1)。有两种设置了 k 位的数字:以 0... 开头的数字。和以 1... 开头的数字.在第一种情况下，下一个 n-1位必须包含那些 k位，在第二种情况下下一个 n-1位只能包含 k-1位。特殊情况当然是0 out of n和 n out of n .

同样的结构可以用来快速告诉我们什么 f(16)一定是。我们已经确定它必须包含 2 个位集，因为它落在 f(10) - f(37) 范围内。 .特别是，它是设置了 2 位的数字 6(像往常一样从 0 开始)。将其定义为范围内的偏移量很有用，因为我们将尝试将该范围的长度从 28 缩小到 1。

我们现在将该范围 segmentation 为 21 个以零开头的值和以 1 开头的 7 个值。由于 6 < 21，我们知道第一位数字是零。在剩下的 7 位中，还有 2 位需要设置，所以我们在三角形中向上移动一条线，看到 15 个值以两个零开始，6 个以 01 开始。由于 6 < 15，f(16) 以 00 开始. 进一步向上，7 <= 10 所以它以 000 开头.但是 6 == 6，所以它不以 0000 开头但是0001 .此时我们改变范围的开始，所以新的偏移量变成0(6-6)

我们知道 need 可以只关注以 0001 开头的数字并有一个额外的位，即 f(16)...f(19) .知道范围是f(16)=00010001, f(17)=00010010, f(18)=00010100, f(19)=00011000应该很明显.

因此，为了计算每一位，我们在三角形中向上移动一行，比较我们的“余数”，根据比较可能向左一列添加零或一。这意味着 f(x) 的计算复杂度是O(bits) , 或 O(log N) ，所需的存储空间为 O(bits*bits) .