创建按位集排序的序列

Question

我正在寻找一种可逆函数unsigned f(unsigned),其中设置的位数f(i)随着i或者至少不减少而增加.显然,f(0)必须是0然后,f(〜0)必须是最后的.在两者之间有更多的灵活性.˚F(0)之后,下一个32个*值必须1U<<0要1U<<31,但我不很在意的顺序(它们都有1位设置).

我想要一个算法,它不需要计算f(0)...f(i-1)以便计算f(i),并且完整的表也是不可行的.

这类似于格雷码,但我看不到重用该算法的方法.我正在尝试使用它来标记大型数据集,并优先考虑我搜索它们的顺序.我的想法是,我有一把钥匙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)的设置方式的数量。这是经典的帕斯卡三角形：kn

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 位的数字：以 a 开头的0...数字和以 开头的数字1...。在第一种情况下，接下来的n-1位必须包含这些k位，在第二种情况下，接下来的n-1位必须仅包含k-1位。特殊情况当然是0 out of n和n out of n。

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

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

我们知道需要只关注以 开头并且有一位额外位的数字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)。