30

在 google protocol buffers 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 位整数

4

6 回答 6

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
于 2010-02-05T23:03:39.750 回答
4

怎么样

(n>>1) - (n&1)*n
于 2010-02-05T22:49:23.910 回答
4

这是另一种做同样的方法，只是为了解释的目的（你显然应该使用 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，之字形编码使用 LSB 作为符号位，其他位作为绝对值（实际上仅适用于正整数，由于 2 的补码，负数的绝对值 -1表示）。

于 2012-09-21T22:31:07.143 回答
2

在摆弄 3lectrologos 提出的公认答案后，我无法在以 unsigned longs 开头（在 C# 中 -- 编译器错误）时让它工作。我想出了类似的东西：

( value >> 1 ) ^ ( ~( value & 1 ) + 1 )

这适用于任何在 2 的补语中表示负数的语言（例如 .NET）。

于 2013-10-30T15:43:43.767 回答
1

我找到了解决方案，不幸的是，这不是我所希望的单线美：

uint signMask = u << 31;
int iSign = *((Int32*)&signMask);
iSign >>= 31;
signMask = *((UInt32*)&iSign);

UInt32 a = (u >> 1) ^ signMask;
return *((Int32*)&a);
于 2010-02-05T22:45:02.183 回答
-1

我确信有一些超高效的按位运算可以更快地完成此操作，但功能很简单。这是一个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]
于 2010-02-05T22:45:43.627 回答