algorithm - 什么算法可以为LUT中的每个任意32位数字节省一位存储空间

Question

一个查找表总共有 4G 条目，它的每个条目都是一个 32 位的任意数字，但它们从不重复。是否有任何算法能够利用每个条目的索引及其（索引）值（32 位数字）使该值的固定位置位始终为零（因此我可以利用该位作为标志来记录某些内容）。我可以通过反向计算来检索 32 位数字。或者退一步说，我是否可以使每两个连续条目的固定位置位始终为零？

我的问题是，是否有任何通用代码可以使每个任意 32 位数字节省 1 位。所以我可以利用这个位作为锁定标志。或者，有没有一种方法可以通过一些计算来利用索引及其查找表条目的值来节省值的 1 位存储。

Answer 1

根本不清楚你在问什么。但是，如果我没看错的话，我也许可以在那里找到一件事可以解决，那就是你有0..2 ³² -1中所有整数的排列。这种排列可以用比直接表示更少的位来表示，直接表示需要32*2 ³²位。有了排列的完美表示，每个都是上限（log ₂ (2 ³² !))位，因为有2 ³²！可能的排列。结果证明，该长度约为直接表示中位的 95.5%。所以每个排列可以表示为大约30.6*2 ³²位，每个字有效地占用多于一位。