Zig Zag解码

Question

在谷歌协议缓冲区编码概述中,他们引入了一种称为"Zig Zag编码"的东西,这种方法采用了具有较小幅度的有符号数,并创建了一系列具有较小幅度的无符号数.

例如

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

这是执行相同操作的另一种方法，仅用于解释目的（显然您应该使用 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表示）。