实现动态位域

问题是在下面的问题中会发生什么。实现动态位域

-int数组的元素可以说是5,5,6,7,9位长（它们是不同的）。

我该如何编码它，以便它需要32位而不是通常的160位？

我也想说，在另一方面（解码方面），我不知道每个元素有多大。那么，如果我收到这样的数据，我该如何解码？或者换句话说，我怎样才能以一种可以轻松解码的方式编码？

来源

2011-12-30 Henok Yemane

如果您还描述了上下文或问题，在哪里应用_this_，您可以获得更有帮助的响应。 – 2011-12-30 07:27:24

我没有时间给出正确答案，但这是一个研究得很好的问题。请参阅Google的“通用代码”。 – Kaganar 2011-12-31 01:30:59

根据元素的最大尺寸，您可以在包含元素位数大小的每个元素之前包含4-6位（如果最大值为4，则为4 < 16，如果为最大值，则为5 < 32，6 if最大尺寸< 64）。作为

解码将是简单的：

读4个比特来确定元件尺寸
读取x比特作为元素（其中，x是元件尺寸）

由于变量的大小，您将无法将数据打包到32个字节，因为您需要为每个元素包含某种大小指示符。在这种情况下，假设您使用4位大小，则将使用52位，这只是160位原始大小的32.5％。

来源

2011-12-30 07:20:27

如果比特这些数字之间的分配是预先已知的，它是简单的：只要把各元素的比特阵列中的适当位置中所得到的INT，这样的（例如，在C++代码）：

unsigned int encoded = (val[0]) | (val[1] << 5) | (val[2] << 10) | 
       (val[3] << 16) | (val[4] << 23);

...假设val是一个int数组，它包含的数字长度为5,5,6,7和9位。解码同样简单：

int decoded[5]; 
decoded[0] = encoded & 0x1F; 
decoded[1] = (encoded >> 5) & 0x1F; 
decoded[2] = (encoded >> 10) & 0x3F; 
decoded[3] = (encoded >> 16) & 0x7F; 
decoded[4] = (encoded >> 23);

如果位长度事先不知道，唯一已知的事实是，它们的比特大小组合是32，那么，对于一般情况下，这是不可能的编码他们变成最多32位;因为你已经需要这个数量的位来存储实际的数字;但你也必须知道编码数字的位长;为此，您需要额外的存储空间。这一切都是有效的，只要这些数字不是多余的并且可以被压缩。

当然有办法使它每个整数的长度小于4个字节;取决于要处理的数字的确切属性，一种或另一种算法可能更适合;这里有几个可能的算法的简短列表：

如果你知道整数可以是最多9位长，你可以使用上面显示的简单方法，但偏移量为9来存储数字;用这种方法你可以得到45位的5个值。
在每个元素之前有一个长度指示符是另一种可能性（如Robert Rouhani所示）
另一个例子是建议在this question（使用Dlugosz' Variable-Length-Integer）
您也可以使用Variable-length quantity。

前两种方法的缺点是它们只能表示固定的最大位数。这种处理属于压缩域，为了进行更多的理论分析，请务必阅读关于该主题的一些文献;正如Kaganar的评论所指出的，这里特别感兴趣的是Universal Codes;上面列表中的最后两个算法就是这样的通用代码。对于5,5,6,7和9位的5个值的例子输入，它们应该让你下降到48位（对于4个值小于8位的4位8位，以及对于9位的1个16位数）。这两种方法对列表上其他方法的优点是它们适用于任意大的号码;可能还有其他大学代码更适合您的目的，请务必查看其他大学代码。

来源

2011-12-30 07:30:17 codeling

我认为将5,5,6,7,9压缩到32位是不可能的。太小的存储空间以适应所有的信息。

首先，我们可以通过观察元素的最大可能位来最小化填充位。如果我们将32位变量用于最大10位元素，那么我们正在浪费22位。我们可以用10位数据类型去除每个元素的22位。

除此之外，还需要一些充气，放气的方案，我认为它不适合像OP的例子那样的小数据或数组。

来源

2011-12-30 09:22:10 9dan

实现动态位域

回答

相关问题