protocol-buffers - protobuffers - protocol buffers array

Buffers de protocolo de Google: codificación en zigzag

Question

De los "tipos firmados" en la codificación - Protocol Buffers - Google Code :

La codificación en zigzag asigna enteros con signo a enteros sin signo de modo que los números con un valor absoluto pequeño (por ejemplo, -1) también tengan un valor de codificación varint pequeño. Lo hace de manera que los "zig-zags" avanzan y retroceden a través de los enteros positivos y negativos, de modo que -1 se codifica como 1, 1 se codifica como 2, -2 se codifica como 3, y así sucesivamente, a medida que Se puede ver en la siguiente tabla:

Signed Original  Encoded As
0                0
-1               1
1                2
-2               3
2147483647       4294967294
-2147483648      4294967295

En otras palabras, cada valor n se codifica utilizando

(n << 1) ^ (n >> 31)

para sint32s, o

(n << 1) ^ (n >> 63)

para la versión de 64 bits.

¿En qué forma (n << 1) ^ (n >> 31) es igual a lo que hay en la tabla? Entiendo que funcionaría para aspectos positivos, pero ¿cómo funciona eso para decir, -1? ¿No sería -1 1111 1111 y (n << 1) 1111 1110 ? (¿El cambio de bits en negativos está bien formado en cualquier idioma?)

No obstante, al usar la fórmula y hacer (-1 << 1) ^ (-1 >> 31) , suponiendo un int de 32 bits, obtengo 1111 1111 , que es de 4 mil millones, mientras que la tabla cree que debería tener 1.

Answer 1

Déjame agregar mis dos centavos a la discusión. Como se señaló en otras respuestas, la codificación en zig-zag puede pensarse como un giro de magnitud de signo. Este hecho se puede utilizar para implementar funciones de conversión que funcionan con enteros de tamaño arbitrario. Por ejemplo, uso el siguiente código en uno de mis proyectos de Python:

def zigzag(x: int) -> int:
    return x << 1 if x >= 0 else (-x - 1) << 1 | 1

def zagzig(x: int) -> int:
    assert x >= 0
    sign = x & 1
    return -(x >> 1) - 1 if sign else x >> 1

Estas funciones funcionan a pesar de que el int de Python no tiene un ancho de bits fijo; en cambio, se extiende dinámicamente. Sin embargo, este enfoque puede ser ineficiente en los lenguajes compilados, ya que requiere ramificación condicional.

Answer 2

Desplazando un entero con signo negativo a la derecha se copia el bit de signo, de modo que

(-1 >> 31) == -1

Entonces,

(-1 << 1) ^ (-1 >> 31) = -2 ^ -1
                       = 1

Esto podría ser más fácil de visualizar en binario (8 bits aquí):

(-1 << 1) ^ (-1 >> 7) = 11111110 ^ 11111111
                      = 00000001

Answer 3

Otra forma de pensar acerca del mapeo en zig zag es que es un ligero giro en una representación de signo y magnitud.

En la asignación en zig zag, el bit menos significativo (lsb) de la asignación indica el signo del valor: si es 0, entonces el valor original no es negativo, si es 1, entonces el valor original es negativo.

Los valores no negativos simplemente se desplazan a la izquierda un bit para dejar espacio para el bit de signo en la lsb.

Para valores negativos, puede hacer el mismo desplazamiento de un bit hacia la izquierda para el valor absoluto (magnitud) del número y simplemente hacer que el lsb indique el signo. Por ejemplo, -1 podría asignarse a 0x03 o 0b00000011, donde lsb indica que es negativo y la magnitud de 1 se desplaza a la izquierda en 1 bit.

Lo feo de esta representación de signo y magnitud es el "cero negativo", asignado como 0x01 o 0b00000001. Esta variante de cero "usa" uno de nuestros valores y desplaza el rango de enteros que podemos representar en uno. Probablemente queramos asignar un caso de cero negativo a -2 ^ 63, para poder representar el rango de complemento de 64b 2 completo de [-2 ^ 63, 2 ^ 63). Eso significa que hemos utilizado una de nuestras valiosas codificaciones de un solo byte para representar un valor que muy, muy, muy raramente se usará en una codificación optimizada para números de pequeña magnitud y hemos introducido un caso especial, que es malo.

Aquí es donde ocurre el giro del zigzag en esta representación de signo y magnitud. El bit de signo todavía está en la lsb, pero para los números negativos, restamos uno de la magnitud en lugar del cero negativo de la carcasa especial. Ahora, -1 se asigna a 0x01 y -2 ^ 63 también tiene una representación de caso no especial (es decir, - magnitud 2 ^ 63 - 1, desplazado a la izquierda un bit, con el conjunto de bits lsb / sign, que es todos los bits establecidos en 1s) .

Entonces, otra forma de pensar acerca de la codificación en zig zag es que es una representación de signo y magnitud más inteligente: el bit de signo se almacena en el lsb, 1 se resta de la magnitud de los números negativos y la magnitud se desplaza a la izquierda un bit.

Es más rápido implementar estas transformaciones utilizando los operadores incondicionales de bit a bit que publicaste en lugar de probar explícitamente el signo, el caso especial que manipula valores negativos (por ejemplo, negar y restar 1, o bitwise no), cambiando la magnitud y luego estableciendo explícitamente el bit de signo lsb. Sin embargo, tienen un efecto equivalente y esta serie de pasos de signos y magnitudes más explícitos podría ser más fácil de entender qué y por qué estamos haciendo estas cosas.

Sin embargo, le advertiré que el cambio de valores negativos en C / C ++ no es portátil y debe evitarse. El cambio a la izquierda un valor negativo tiene un comportamiento indefinido y el cambio a la derecha un valor negativo tiene un comportamiento definido por la implementación. Incluso el desplazamiento a la izquierda de un entero positivo puede tener un comportamiento indefinido (p. Ej., Si cambia al bit de signo puede causar una trampa o algo peor). Por lo tanto, en general, no modifique los tipos firmados en C / C ++. "Solo di no."

Pase primero a la versión no firmada del tipo para obtener resultados seguros y bien definidos de acuerdo con el estándar. Esto significa que no tendrá un cambio aritmético de valores negativos, solo un cambio lógico, por lo que necesita ajustar la lógica para tenerlo en cuenta.

Aquí están las versiones seguras y portátiles de las asignaciones de zigzag para enteros de 64b en C (note la negación aritmética):

#include <stdint.h>

uint64_t zz_map( int64_t x )
{
  return ( ( uint64_t ) x << 1 ) ^ -( ( uint64_t ) x >> 63 );
}

int64_t zz_unmap( uint64_t y )
{
  return ( int64_t ) ( ( y >> 1 ) ^ -( y & 0x1 ) );
}