Zig Zag Décodage

Question

Dans les tampons de protocole Google encodage aperçu , ils introduisent quelque chose appelé « Zig Zag Encoding », cela prend des nombres signés, qui ont une faible amplitude, et crée une série de numéros non signés qui ont une faible amplitude.

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 assez intelligent, il est:

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

Je comprends comment cela fonctionne, mais je ne peux pas pour la vie de me comprendre comment inverser cela et le décoder de nouveau dans signés entiers 32 bits,

Answer 1

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

Je reçois les résultats suivants:

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

Answer 2

Qu'en est-

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

Answer 3

est ici encore une autre façon de faire la même chose, seulement à des fins d'explication (vous devez évidemment utiliser une doublure de 3lectrologos).

Il suffit de remarquer que vous XOR avec un nombre qui est soit tout 1 de (équivalent à Négation binaire) ou tout 0 s (équivalent à ne rien faire). C'est ce que (-(n & 1)) rendements, 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;
}

Ainsi, afin d'avoir un bon nombre de 0 est sur les positions les plus importantes, le codage en zigzag utilise les LSB comme bit de signe, et les autres bits que la valeur absolue (uniquement pour des nombres entiers positifs en fait, et la valeur absolue -1 pour les nombres négatifs dus 2 de la représentation du complément).

Answer 4

Après tripoter la réponse acceptée proposée par 3lectrologos, je ne pouvais pas le faire fonctionner en commençant par languit 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 toutes les langues qui représente les nombres négatifs dans le compliment de 2 (par exemple .NET).

Answer 5

Je l'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);

Answer 6

Je suis sûr qu'il ya des opérations au niveau du bit super efficace qui font plus rapidement, mais la fonction est simple. Voici une implémentation 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]