Google Protocole Buffers: ZigZag encodage

StackOverflow https://stackoverflow.com/questions/4533076

Question

De "Types signés" à la encodage - Protocol Buffers - Google Code :

  

Zigzag codage maps entiers signés à des entiers non signés de sorte que les nombres avec une petite valeur absolue (par exemple, -1) ont une faible valeur codée varint aussi. Il fait cela d'une manière qui « zig-zags » d'avant en arrière à travers les nombres entiers positifs et négatifs, de sorte que -1 est codé en tant que 1, 1 est codé en tant que 2, -2 est codé sous la forme 3, et ainsi de suite, comme vous peut voir dans le tableau suivant: 

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

En d'autres termes, chaque valeur n est codé en utilisant

     

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

     

pour sint32s ou

     

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

     

pour la version de 64 bits.

Comment (n << 1) ^ (n >> 31) égale ce qui est dans la table? Je comprends que travaillerais positifs, mais comment ce travail pour dire, -1? Ne -1 être 1111 1111 et (n << 1) être 1111 1110? (Bit-décalage est sur les négatifs bien formés dans toutes les langues?)

Néanmoins, en utilisant le fomula et faire (-1 << 1) ^ (-1 >> 31), en supposant un int 32 bits, je reçois 1111 1111, qui est de 4 milliards, alors que la table pense que je devrais avoir 1.

Était-ce utile?

La solution

Déplacement d'un entier signé de négatif à droite copies le bit de signe, de sorte que 

(-1 >> 31) == -1

Alors, 

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

Cela peut être plus facile à visualiser en binaire (8 bits ici): 

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

Autres conseils

Une autre façon de penser à la cartographie zig zag est qu'il y a une légère torsion sur un signe et une représentation grandeur.

zig zag cartographie, le bit le moins significatif (LSB) de la cartographie indique le signe de la valeur: si elle est à 0, la valeur d'origine est non-négatif, si elle est 1, alors la valeur initiale est négative.

Les valeurs non-négatives sont simplement laissés déplacé un peu pour faire de la place pour le bit de signe dans le lsb.

Pour les valeurs négatives, vous pouvez faire la même chose un bit décalage vers la gauche pour la valeur absolue (magnitude) du nombre et ont simplement lsb indiquer le signe. Par exemple, la carte pourrait -1 à 0x03 ou 0b00000011, où le lsb indique qu'il est négatif et l'ampleur de 1 est laissé décalé de 1 bit.

La chose laide de cette représentation signe et la valeur est « zéro négatif » cartographié comme 0x01 ou 0b00000001. Cette variante de zéro « consomme » une de nos valeurs et décale la plage d'entiers, nous pouvons représenter par un. Nous voulons probablement à la carte cas particulier zéro négatif à -2 ^ 63, afin que nous puissions représenter le complément de la pleine 64b 2 plage de [-2 ^ 63, 2 ^ 63). Cela signifie que nous avons utilisé l'un de nos précieux encodages un seul octet pour représenter une valeur qui sera très, très, très rarement utilisé dans un encodage optimisé pour un petit nombre de grandeur et nous avons mis en place un cas particulier, ce qui est mauvais.

est où la torsion de zig zag sur cette représentation des signes et de l'ampleur se produit. Le bit de signe est toujours dans le lsb, mais pour les nombres négatifs, nous soustrayons un de l'ampleur plutôt qu'une enveloppe spéciale négative zéro. Maintenant, -1 cartes à 0x01 et -2 ^ 63 a une représentation de cas non spécial trop (ie - magnitude 2 ^ 63 - 1, à gauche décalé d'un bit, avec lsb / signe bit, ce qui est de tous les bits mis à 1 s) .

Ainsi, une autre façon de penser à zig zag codage est qu'il est un signe plus intelligente et la représentation amplitude: le bit de signe est stocké dans le lsb, 1 est soustrait de l'amplitude des nombres négatifs, et l'amplitude est laissé décalé d'une bit.

Il est plus rapide à mettre en œuvre ces transformations en utilisant les opérateurs binaires inconditionnel que vous avez posté plutôt que de tester explicitement le signe, cas particulier la manipulation de valeurs négatives (par exemple - Négation et soustraire 1 ou Négation binaire), le déplacement de l'ampleur, et puis définir explicitement le lsb bit de signe. Cependant, ils sont équivalents en vigueur et ce signe plus explicite et une série ampleur des mesures qui pourraient être plus faciles à comprendre quoi et pourquoi nous faisons ces choses.

Je vous préviens que si peu de décalage des valeurs négatives en C / C ++ n'est pas portable et doit être évité. Gauche décalant une valeur négative a un comportement non défini et décalage vers la droite une valeur négative a défini le comportement de mise en œuvre. Même laissé le déplacement d'un nombre entier positif peut avoir un comportement non défini (par exemple - si vous passez dans le bit de signe qu'il pourrait causer un piège ou quelque chose de pire). Donc, en général, ne se déplace pas peu types signés en C / C ++. "Dis juste non."

Cast d'abord à la version non signée du type d'avoir des résultats sûrs, bien définis selon la norme. Cela ne signifie pas que vous aurez alors pas décalage arithmétique des valeurs négatives -. Que décalage logique, vous devez régler la logique compte que

Voici les versions sûres et portables du zig zag correspondances pour les entiers de 64b en C (note la négation arithmétique): 

#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 ) );
}

Permettez-moi d'ajouter mes deux cents à la discussion. Comme d'autres réponses ont noté, le zig-zag le codage peut être considéré comme une torsion signe de grandeur. Ce fait peut être utilisé pour mettre en œuvre des fonctions de conversion qui travaillent pour les entiers de taille arbitraire. Par exemple, j'utilise le code suivant dans un de mes projets 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

Ces fonctions fonctionnent malgré la int de Python ne fixe largeur de bit; à la place, elle étend dynamiquement. Cependant, cette approche peut être inefficace dans les langages compilés car il nécessite un branchement conditionnel.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top