语言无关 – Zig Zag解码

在google协议缓冲区 encoding overview中，它们引入了一种名为“Zig Zag Encoding”的东西，它采用了有序数字的有符号数字，并创建了一系列幅度较小的无符号数。

例如

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位整数

试试这个：

(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