9

我正在寻找一个可逆函数unsigned f(unsigned)，其设置的位数f(i)随着 增加i，或者至少不减少。显然，f(0)那么必须为 0，并且 f(~0) 必须排在最后。两者之间有更大的灵活性。在 f(0) 之后，接下来的 32* 值必须是1U<<0to 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.
4

2 回答 2

2

好吧，看来我有一个合理的答案。首先让我们定义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)to 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 个值以两个 0 开头，6 个以 01 开头。由于 6 < 15，f(16) 以 00 开头. 再往上走，7 <= 10 所以它以 . 开头000。但是 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)这意味着isO(bits)或的计算复杂度O(log N)以及所需的存储空间是O(bits*bits)。

于 2013-10-11T09:16:15.430 回答
1

对于每个给定的数字k，我们知道有binom(n, k) n位整数的k位值恰好为 1。我们现在可以生成一个n + 1整数查找表，该表存储每个k数字有多少位少。然后可以使用该查找表来查找o的一位数f(i)。

一旦我们知道这个数字，我们就减去这个位数的查找表值，从中我们得到具有给定位数的数字i的排列索引。p尽管我还没有在这方面进行过研究，但我很确定存在一种方法来查找 a 的 pth 置换，该置换在最低位std::vector<bool>用零和一初始化。o

反向功能

查找表再次派上用场。我们可以通过计算输入整数中的一位并读取查找表来直接计算前面少一位数的个数。然后你“只”需要确定排列索引并将其添加到查找的值中，你就完成了。

免责声明

当然，这只是一个粗略的大纲，某些部分（尤其是涉及排列的部分）可能需要比听起来更长的时间。

添加

你说你自己

我试图用它来标记一个大型数据集，并优先考虑我搜索它们的顺序。

这对我来说听起来好像你会从低汉明距离到高汉明距离。在这种情况下，有一个增量版本就足够了，它从前一个数字生成下一个数字：

unsigned next(unsigned previous)
{
    if(std::next_permutation(previous))
        return previous;
    else
        return (1 << (1 + countOneBits(previous))) - 1;
}

当然std::next_permutation排列不能以这种方式工作，但我认为我的意思很清楚我的意思是如何使用它。

于 2013-10-10T14:26:37.827 回答