Почему я не могу сбросить & # 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 < < 22), происходит перенос ...

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

Который затем кодируется. Затем позже вы можете получить обратно из c и p:

a = c+p =      100000000000000000000001

но поскольку он хранится в 23-разрядном целом числе, это эквивалентно:

a =             00000000000000000000001

который является оригиналом.