¿Por qué puedo "plegar" un rango de enteros en la mitad del tamaño sin perder información?

Question

Estoy intentando entender un documento sobre la pérdida de datos comprima los números de punto flotante y quede atrapado en un paso en particular, donde los autores asignan un número entero con signo de un rango determinado a un rango de la mitad del tamaño, perdiendo la información que creo que es necesaria. Tengo la sensación de que los autores están usando una técnica estándar que es tan obvia para su audiencia que no se molestan en explicar, pero que es completamente opaca para mí.

El valor que se está " plegado " es la diferencia entre dos enteros positivos de 23 bits (las mantisas de un valor de punto flotante predicho y real) que se encuentra entre 1 - 2 ²³ y 2 ²³ - 1. Los autores mueven los números con los valores más altos (negativo y positivo) " hacia adentro " ;, por lo que el rango resultante es la mitad del tamaño y cada número (excepto 0) se asigna a dos valores posibles del rango original. Esto me hace preguntarme cómo debería invertirse el proceso para determinar el valor original. En las propias palabras de los autores:

  

Calculamos el corrector firmado que es el módulo 2 ²³ más corto y el número k que especifica el intervalo más estrecho (1-2 ^k , 2 ^k ) en el que cae este corrector. A continuación, este número k , que oscila entre 0 y 22 se comprime [...]. Finalmente, se comprimen los bits significativos del corrector k + 1 .

El pseudocódigo para esto se da como:

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
}

Ignorando el método de compresión real, la salida consiste en c y k . Lo que no entiendo es: ¿Cómo puedo restaurar el c original de c y k cuando " encierra c en " ; ¿La parte superior simplemente asigna la mitad del rango potencial a la otra mitad? Lo intenté en papel con 4 en lugar de 23 bits y simplemente no lo entiendo.

Answer 1

Cuando el autor dice que están considerando los significandos "módulo 2 ^ 23", eso significa que los números se almacenarán en números enteros de 23 bits, por lo que los números que difieren en múltiplos de 2 ^ 23 serán "iguales" ya que el patrón de bits es el mismo. (Consulte http://mathworld.wolfram.com/ModularArithmetic.html )

Desde el " envoltura " el código después de c = a-p solo agrega o resta 2 ^ 23 a c, cuando luego lo inviertas al calcular a = c + p, obtienes el valor correcto ya que 2 ^ 23 no importa.

Aquí hay un ejemplo en binario ...

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

entonces, como c < = - (1 < < 22), se produce el ajuste ...

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

Que luego se codifica. Luego, más tarde, puedes recuperar a de cyp:

a = c+p =      100000000000000000000001

pero como esto se almacena en un entero de 23 bits, esto es equivalente a:

a =             00000000000000000000001

que es el original a.