为什么我可以“折叠”将一系列整数缩小为一半大小而不丢失信息？

Question

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

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

我们计算最短模 2²³ 的有符号校正器和指定最紧间隔的数字 k (1-2^k , 2^k) 该校正器属于其中。接下来，这个范围在 0 到 22 之间的数字k被压缩[...]。最后，校正器的 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=ap 之后的代码仅对 c 加或减 2^23，当您稍后通过计算 a = c+p 来反转它时，您会得到正确的值，因为 2^23 并不重要。

这是二进制的示例...

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

然后，由于 c<=-(1<<22)，因此发生换行...

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

然后对其进行编码。然后，您可以从c和p返回a：

a = c+p =      100000000000000000000001

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

a =             00000000000000000000001

这是原始的a。