Zig Zag解码

Question

在谷歌协议缓冲区encoding overview中，他们引入了一种叫做"Zig编码“的东西，它接受有符号的数字，这些数字的幅度很小，并产生一系列没有符号的数字，这些数字的幅度很小。

例如

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

诸若此类。他们为此提供的编码函数相当聪明，它是：

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

我知道这是如何工作的，然而，我无论如何也想不出如何反转它，并将其解码回有符号的32位整数

Answer 1

试试这个：

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

编辑：

我发布了一些示例代码以供验证：

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

我得到了以下结果：

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

Answer 2

怎么样

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

Answer 3

这里还有另一种方法来做同样的事情，只是为了解释(你显然应该使用3lectrologos的一行代码)。

你只需要注意你对一个数字进行异或运算，这个数字要么全是1(相当于按位非)，要么全是0(相当于什么都不做)。这就是(-(n & 1))产生的结果，或者说谷歌的“算术转移”言论解释了这一点。

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

因此，为了在最重要的位置上有许多0，zigzag编码使用LSB作为符号位，其他位作为绝对值(实际上仅对于正整数，由于2的补码表示，负数的绝对值为-1 )。