Décodage Zig Zag
Dans les tampons de protocole google Vue d'ensemble de l'encodage , ils introduisent quelque chose appelé "codage Zig Zag", cela prend des nombres signés, qui ont une petite magnitude, et crée une série de nombres non signés qui ont une petite magnitude.
Par exemple
Encoded => Plain
0 => 0
1 => -1
2 => 1
3 => -2
4 => 2
5 => -3
6 => 3
Et ainsi de suite. La fonction d'encodage qu'ils donnent pour cela est plutôt intelligente, c'est:
(n << 1) ^ (n >> 31) //for a 32 bit integer
Je comprends comment cela fonctionne, cependant, je ne peux pas pour la vie de moi comprendre comment inverser cela et le décoder retour dans les entiers 32 bits signés
6 réponses
Essayez celui-ci:
(n >> 1) ^ (-(n & 1))
Modifier:
Je poste un exemple de code pour la vérification:
#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;
}
J'obtiens les résultats suivants:
0 => 0
1 => -1
2 => 1
3 => -2
4 => 2
5 => -3
6 => 3
7 => -4
8 => 4
9 => -5
Voici encore une autre façon de faire la même chose, juste à des fins d'explication (vous devriez évidemment utiliser le One-liner de 3lectrologos).
Vous devez juste remarquer que vous xor avec un nombre qui est soit tous les 1 (équivalent à bitwise not) ou tous les 0 (équivalent à ne rien faire). C'est ce que (-(n & 1)) rapporte, ou ce qui est expliqué par la remarque de "décalage arithmétique" 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;
}
Donc, afin d'avoir beaucoup de 0 sur les positions les plus significatives, l'encodage en zigzag utilise le LSB comme bit de signe, et les autres bits comme valeur absolue (seulement pour les entiers positifs en fait, et la valeur absolue -1 pour les nombres négatifs en raison de la représentation du complément 2).
J'ai trouvé une solution, malheureusement ce n'est pas la beauté d'une ligne que j'espérais:
uint signMask = u << 31;
int iSign = *((Int32*)&signMask);
iSign >>= 31;
signMask = *((UInt32*)&iSign);
UInt32 a = (u >> 1) ^ signMask;
return *((Int32*)&a);
Après avoir manipulé la réponse acceptée proposée par 3lectrologos, Je ne pouvais pas la faire fonctionner en commençant par des longs non signés (en C # -- Erreur du compilateur). Je suis venu avec quelque chose de similaire à la place:
( value >> 1 ) ^ ( ~( value & 1 ) + 1 )
Cela fonctionne très bien pour toute langue qui représente des nombres négatifs dans le compliment de 2 (par exemple. Net).
Je suis sûr qu'il y a des opérations bit à bit super efficaces qui le font plus rapidement, mais la fonction est simple. Voici une implémentation 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]