language agnostic - protobuffers - Decodificación Zig Zag

protocol buffer list

Question

En la descripción general de codificación de búferes de protocolo de Google, introducen algo llamado "Codificación Zig Zag", que toma números con signo, que tienen una magnitud pequeña, y crea una serie de números sin signo que tienen una magnitud pequeña.

Por ejemplo

Encoded => Plain
0 => 0
1 => -1
2 => 1
3 => -2
4 => 2
5 => -3
6 => 3

Y así. La función de codificación que dan para esto es bastante inteligente, es:

(n << 1) ^ (n >> 31) //for a 32 bit integer

Entiendo cómo funciona esto, sin embargo, no puedo, por mi vida, descubrir cómo revertir esto y decodificarlo de nuevo en enteros de 32 bits con signo

Answer 1

Después de juguetear con la respuesta aceptada propuesta por 3lectrologos, no pude hacer que funcionara al comenzar con largos sin firmar (en C # - error del compilador). Se me ocurrió algo similar en su lugar:

( value >> 1 ) ^ ( ~( value & 1 ) + 1 )

Esto funciona muy bien para cualquier idioma que represente números negativos en el complemento de 2 (por ejemplo, .NET).

Answer 2

Esta es otra forma de hacer lo mismo, solo para propósitos de explicación (obviamente, debes usar el formato de 3lectrologos).

Solo debes notar que estás con un número que es todos los 1 (equivalente a bitwise no) o todos los 0 (equivalente a no hacer nada). Eso es lo que (-(n & 1)) produce, o lo que se explica por el comentario "cambio aritmético" de Google.

int zigzag_to_signed(unsigned int zigzag)
{
    int abs = (int) (zigzag >> 1);

    if(zigzag % 2)
        return ~abs;
    else
        return abs;
}

unsigned int signed_to_zigzag(int signed)
{
    unsigned int abs = (unsigned int) signed << 1;

    if(signed < 0)
        return ~abs;
    else
        return abs;
}

Así que para tener un montón de 0 en las posiciones más significativas, la codificación en zigzag usa el LSB como bit de signo y los otros bits como el valor absoluto (solo para enteros positivos en realidad, y el valor absoluto -1 para números negativos debido al complemento de 2 representación).

Answer 3

Estoy seguro de que hay algunas operaciones bitwise súper eficientes que hacen esto más rápido, pero la función es sencilla. Aquí hay una implementación de python:

def decode(n):
  if (n < 0):
    return (2 * abs(n)) - 1
  else:
    return 2 * n

>>> [decode(n) for n in [0,-1,1,-2,2,-3,3,-4,4]]
[0, 1, 2, 3, 4, 5, 6, 7, 8]

Answer 4

He encontrado una solución, desafortunadamente no es la única línea que esperaba:

uint signMask = u << 31;
int iSign = *((Int32*)&signMask);
iSign >>= 31;
signMask = *((UInt32*)&iSign);

UInt32 a = (u >> 1) ^ signMask;
return *((Int32*)&a);

Answer 5

Prueba este:

(n >> 1) ^ (-(n & 1))

Editar:

Estoy publicando un código de ejemplo para verificación:

#include <stdio.h>

int main()
{
  unsigned int n;
  int r;

  for(n = 0; n < 10; n++) {
    r = (n >> 1) ^ (-(n & 1));
    printf("%u => %d/n", n, r);
  }

  return 0;
}

Obtengo los siguientes resultados:

0 => 0
1 => -1
2 => 1
3 => -2
4 => 2
5 => -3
6 => 3
7 => -4
8 => 4
9 => -5

Answer 6

Qué tal si

(n>>1) - (n&1)*n