compression - 为什么我可以将 "fold"范围内的整数变成二分之一大小而不丢失信息？

Question

我正在努力理解 a paper on lossless compression of floating point numbers并卡在一个特定的步骤，作者将一个带符号的整数从某个范围映射到一半大小的范围，丢失了我认为需要的信息。我有一种感觉，作者正在使用一些标准技术，这些技术对他们的听众来说是显而易见的，以至于他们懒得解释，但对我来说却完全不透明。

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

We compute the signed corrector that is the shortest modulo 2²³ and the number k that specifies the tightest interval (1-2^k , 2^k) into which this corrector falls. Next, this number k, which ranges between 0 to 22 is compressed [...]. Finally the k + 1 significant bits of the corrector are compressed.

伪代码如下:

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组成。我没有得到的是:当“wrap c into”时，如何从 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<<22)，发生了换行...

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

然后对其进行编码。然后稍后，您可以从 c 和 p 取回 a:

a = c+p =      100000000000000000000001

但是因为它存储在一个 23 位整数中，所以这相当于:

a =             00000000000000000000001

这是原来的a。