如何将一个长整数映射到一个由较小整数组成的N维向量中（并快速求逆）？

Question

给定一个由小整数组成的N维向量，有没有一种简单的方法将其与一个大整数一对一地映射？

比如说，我们有一个3维向量空间。我们能否使用一个整数(int48)y来表示向量X=[(int16)x1,(int16)x2,(int16)x3]？显然答案是“可以”。但问题是：“如何以最快的方式进行这个操作，并且它的反操作是什么？”

这个新的一维空间会拥有一些非常特殊和有用的属性吗？

- psihodelia

---

我的直觉告诉我要用位移操作。但我不是一个狂热的C程序员。 - Xavier Ho

@sth：OP没有说“作为整数”，而是“使用整数”。要有意义地表示向量仍需要解包。 - Xavier Ho

@Xavier：OP说他想用一个48位的整数来表示一个由三个32位整数组成的向量。对我来说，这一点并不明显。此外，问题中提到了欧几里得度量，这可能意味着*y = |X|*，但这并不是一一对应的。 - sth

@sth：很好。让我们看看OP是否愿意回答你的问题。=] - Xavier Ho

一个32位数字有2^32个不同的值，因此三个32位数字会有(2^32)^3 = 2^96种组合。一个28位数字有2^48个不同的值，远远小于2^92。因此，没有实际上具有反函数的映射。这是不可能的。 - Joren

Answer 1

对于上面的例子，您有3 * 32 = 96位信息，因此在没有任何先验知识的情况下，您需要96位才能获得等效的长整数。

然而，如果您知道您的x1、x2、x3值始终适合16位，那么您可以将它们全部打包成48位整数。

无论哪种情况，技术都非常简单，只需使用移位、掩码和按位或运算来打包/解包值。

- Paul R

---

看起来我们的直觉产生了冲突。;] - Xavier Ho

Answer 2

为了更具体地说明，如果您有一个由8位数字组成的三维向量，就像这样：

uint8_t vector[3] = { 1, 2, 3 };

然后，您可以像这样将它们合并为一个单一的24位数字：

uint32_t all = (vector[0] << 16) | (vector[1] << 8) | vector[2];

这个数字如果使用以下语句打印出来：

```python print(number) ```

printf("the vector was packed into %06x", (unsigned int) all);

生成输出

the vector was packed into 010203

反向操作将如下所示：

uint8_t v2[3];

v2[0] = (all >> 16) & 0xff;
v2[1] = (all >> 8) & 0xff;
v2[2] = all & 0xff;

当然，这完全取决于向量中的个别数字的大小和向量长度是否超过可用整数类型的大小，否则您将无法将“打包”向量表示为单个数字。

- unwind

Answer 3

如果你有大小为Ci=|Si|的集合Si，其中i=1..n，则笛卡尔积集合S=S1 x S2 x ... x Sn的大小为C=C1 * C2 * ... * Cn。

这激发了一种明显的一对一打包方法。如果每个集合中都有元素e1,...,en，范围在0到Ci-1之间，则将元素e=(e1,...,en)赋值为e1+C1*(e2 + C2*(e3 + C3*(...Cn*en...)))。

你可以进行任何此打包的排列，但除非这些值完全相关，否则完整集合的大小必须是组成集合大小的乘积。

在三个32位整数的特定情况下，如果它们可以取任何值，则应将它们视为一个96位整数。

如果你特别想，你可以通过任意数量的方式将小值映射到小值（例如，用L1范数填充球体），但你必须指定想要拥有的属性。

（例如，可以将(n,m)映射到(max(n,m)-1)^2 + k，其中如果n<=m，则k=n，如果n>m，则k=n+m--你可以将其绘制为填充正方形的图像）

1 2 5   | draw along the edge of the square this way
4 3 6   v
  8 7

如果你从1开始计数，并且只考虑正数值；对于整数，你可以绕着原点螺旋前进。

- Rex Kerr

---

请注意，“显然的打包”方法是其他答案中显示的移位和掩码方法的概括 - 这些答案假定Cx = C1 = C2 = C3 ...，其中Cx是2的幂（因此可以通过移位进行乘法，通过按位或进行加法）。一般形式可能更普遍地有用。 - caf

@caf - 感谢您指出这一点。在我的回答中，我可能应该更清楚地表明这个事实。 - Rex Kerr

Answer 4

为了扩展 Rex Kerr的通用形式，在C语言中，您可以这样打包数字：

X = e[n];

X *= MAX_E[n-1] + 1;
X += e[n-1];

/* ... */

X *= MAX_E[0] + 1;
X += e[0];

然后使用以下代码进行解压：

e[0] = X % (MAX_E[0] + 1);
X /= (MAX_E[0] + 1);

e[1] = X % (MAX_E[1] + 1);
X /= (MAX_E[1] + 1);

/* ... */

e[n] = X;

(其中MAX_E[n]是e[n]可能具有的最大值)。请注意，这些最大值很可能是常数，并且对于每个e可能相同，这将使事情变得简单一些。

其他答案中给出的移位/掩码实现是这个问题的一般化，适用于MAX_E + 1值为2的幂的情况（因此可以使用移位进行乘法和除法，使用按位或进行加法，使用按位与进行模数运算）。

- caf

Answer 5

我在没有时间检查细节的情况下编写这篇文章，但我怀疑最好的方法是使用模算术来表示您的长整数，使用k个互质的不同整数。然后可以使用中国剩余定理重构原始整数。很抱歉这有点草率，但希望能有所帮助。

- Nathan

Answer 6

#include <stdint.h> // for uint8_t
long x;
uint8_t * p = &x;

或者

union X {
   long L;
   uint8_t A[sizeof(long)/sizeof(uint8_t)];
};

如果您不关心字节序，则可以使用该方法。根据我的经验，编译器使用联合会生成更好的代码，因为它不会像快速设置“您获取了此地址，因此我必须将其保留在RAM中”的规则一样。如果您尝试使用编译器无法优化的内容索引数组，则会触发这些规则。

如果您关心字节序，则需要进行掩码和移位操作。

- nategoose

Answer 7

有一些完全不可移植的方法可以使用打包联合和直接访问内存来使其真正快速。你真的需要这种速度是可疑的。使用移位和掩码的方法对于大多数目的来说应该已经足够快了。如果不行，考虑使用专门的处理器，如GPU，其中向量支持得到了优化（并行）。

这种天真的存储方式除了我能预见到的可以同时对三个坐标执行一些计算（加、减、逻辑位运算）以外，没有任何有用的属性，只要你只使用正整数并且在加法和减法中不会溢出。

你最好确信你不会溢出（或者不会因为减法而变成负数），否则向量将变成垃圾。

- kriss

Answer 8

我认为你想要的可以使用多维空间填充曲线来解决。该链接提供了许多参考资料，这些资料又提供了不同的方法和见解。这里有一个可逆映射的具体示例。它适用于任何维度N。

至于有用的属性，这些映射与格雷码相关。

很难说这是否是你正在寻找的，或者“将3个16位整数打包成48位整数”是否适合你的需求。

- brainjam