为什么我不能折叠＆＃8221;一系列整数变成一半大小而不丢失信息？

Question

我正在尝试理解关于无损的论文压缩浮点数并陷入某一特定步骤，在这一步中，作者将某个范围内的有符号整数映射到一半大小的范围内，丢失了我认为需要的信息。我觉得作者正在使用一些标准技术，这对他们的观众来说是显而易见的，他们无需解释，但这对我来说是完全不透明的。

正在“折叠”的价值是两个23位正整数（预测和实际浮点值的尾数）之间的差异，它位于1 - 2 ²³ 和2 ²³ - 1之间。作者将具有最高值（负和正）的数字“向内”移动，因此得到的范围是大小的一半，并且每个数字（除了0）映射到来自原始范围的两个可能值。这让我想知道如何反转过程以确定原始值。在作者自己的话中：

  

我们计算最短模2 ²³ 的有符号校正器和指定最紧密间隔的数字 k （1-2 ^k ，2 ^k ）这个校正器落入其中。接下来，压缩[...]的数字 k ，范围在0到22之间。最后，校正器的 k + 1 有效位被压缩。

这个伪代码如下：

void comp mantissa(int expo, int a, int p) {
  // c will be within [1-2^23 ... 2^23 -1]
  int c = a - p;
  // wrap c into [1-2^22 ... 2^22 ]
  if (c <= -(1<<22)) c += 1<<23;
  else if (c > (1<<22)) c -= 1<<23;
  // find tightest [1-2^k ... 2^k ] containing c
  int k = 0;
  // loop could be replaced with faster code
  int c1 = (c < 0 ? -c : c);
  while (c1) { c1 = c1 >> 1; k++ }
  // adjust k for case that c is exactly 2k
  if (k && (c == 1<<(k-1))) k--;

  // .. further code omitted for brevity
}

忽略实际的压缩方法，输出包含 c 和 k 。我没有得到的是：当“包装c进入”时，如何从 c 和 k 恢复原始 c ;上面的部分只是将潜在范围的一半映射到另一半？我在纸上用4而不是23位尝试了这个，我只是没有得到它。

Answer 1

当作者说他们正在考虑有效数“模2 ^ 23”时，这意味着数字将以23位整数存储，因此相差2 ^ 23的数字的数字将是“相同的”。因为位模式是相同的。 （参见 http://mathworld.wolfram.com/ModularArithmetic.html ）

由于“包裹”而c = a-p之后的代码只增加或减去2 ^ 23到c，当你稍后通过计算a = c + p来反转它时你会得到正确的值，因为2 ^ 23并不重要。

这是二进制的一个例子......

a =             00000000000000000000001
p =             10000000000000000000100
c = a-p =      -10000000000000000000011

然后，由于c <= - （1 <＆lt; 22），包裹发生......

c = c+(1<<23) = 11111111111111111111101

然后编码。然后，你可以从c和p中找回一个：

a = c+p =      100000000000000000000001

但由于它存储在23位整数中，因此相当于：

a =             00000000000000000000001

这是原来的。