算术压缩中将 1 位移至高位，将 0 位移至低位

Question

我正在尝试编写自己的算术压缩器。我通过引用我发现的实现来作弊。具体来说，这部分：

（请注意，此代码不完整，作者后来更新了此代码以使其完整，但就我的问题而言，这部分就足够了。）

  unsigned int high = 0xFFFFFFFFU;
  unsigned int low = 0;
  char c;
  while ( input >> c ) {
    int range = high - low + 1;
    prob p = model.getProbability(c);
    high = low + (range * p.upper)/p.denominator;
    low = low + (range * p.lower)/p.denominator;
    for ( ; ; ) {
      if ( high < 0x80000000U )
        output_bit( 0 );
      else if ( low >= 0x80000000U )
        output_bit( 1 );
      else
        break;
      low <<= 1;
      high << = 1;
      high |= 1;
    }
  }

在这段代码下面，作者有如下描述：

我们将 1 移入高位的最低有效位，将 0 移入低位的最低有效位。因此，我们通过排除不再对计算精度有任何贡献的位来继续研究 32 位精度。在这个特定的实现中，我们只在工作寄存器中保留 32 位，其中一些附加数字已发送到输出，还有一些其他数字等待输入。

我对此有几个问题。首先，我不太明白为什么我们将

1

而不是

0

转变为

high

。是因为我们想要最大化

high

的值吗？其次，作者似乎声称

0

已移至

low

的最低有效位，但我没有看到这是在哪里明确完成的，如果没有明确完成，我不明白上述算法是如何实现的保证

low

的最低有效位为 0？

Answer 1

1. 是的，就是最大化

   low

   和

   high

   之间的距离。

2. <<= 1

   始终将零移至低位。