Tha*_*tos 19 bit-shift protocol-buffers zigzag-encoding
来自编码的 "签名类型" - 协议缓冲区 - Google代码:
ZigZag编码将有符号整数映射到无符号整数,因此具有较小绝对值(例如,-1)的数字也具有较小的varint编码值.它通过正负整数来回"zig-zags"的方式做到这一点,因此-1被编码为1,1被编码为2,-2被编码为3,依此类推,就像你一样可以在下表中看到:
Run Code Online (Sandbox Code Playgroud)Signed Original Encoded As 0 0 -1 1 1 2 -2 3 2147483647 4294967294 -2147483648 4294967295换句话说,使用编码每个值n
(n << 1) ^ (n >> 31)对于sint32s,或
(n << 1) ^ (n >> 63)对于64位版本.
如何(n << 1) ^ (n >> 31)什么表中的平等吗？我明白这对积极因素有用,但是这怎么说呢,-1？不会-1 1111 1111,(n << 1)是1111 1110吗？(在任何语言中形成的负片都有点转移吗？)
尽管如此,使用公式和做(-1 << 1) ^ (-1 >> 31),假设一个32位的int,我得到1111 1111,这是40亿,而表认为我应该有1.
Gre*_*ill 31
将负有符号整数向右移位会复制符号位,这样就可以了
(-1 >> 31) == -1
然后,
(-1 << 1) ^ (-1 >> 31) = -2 ^ -1
= 1
这可能更容易以二进制形式显示(这里是8位):
(-1 << 1) ^ (-1 >> 7) = 11111110 ^ 11111111
= 00000001
考虑之字形映射的另一种方式是，它是符号和幅度表示的轻微扭曲。
在 Zig Zag 映射中，映射的最低有效位 (lsb) 指示值的符号：如果为 0，则原始值是非负的，如果为 1，则原始值是负的。
非负值只需左移一位，为 lsb 中的符号位腾出空间。
对于负值，您可以对数字的绝对值（大小）执行相同的左移一位，并简单地让 lsb 指示符号。例如，-1 可以映射到 0x03 或 0b00000011，其中 lsb 表示它是负数，并且 1 的大小左移 1 位。
这个符号和幅度表示的丑陋之处在于“负零”，映射为 0x01 或 0b00000001。这种零的变体“用完了”我们的一个值，并改变了我们可以用一表示的整数范围。我们可能希望将负零映射到 -2^63 的特殊情况，以便我们可以表示 [-2^63, 2^63) 的完整 64b 2 的补码范围。这意味着我们使用了一种有价值的单字节编码来表示一个值，该值很少用于针对小数值优化的编码中，并且我们引入了一种特殊情况，这是很糟糕的。
这就是符号和幅度表示中锯齿形扭曲发生的地方。符号位仍在 lsb 中，但对于负数，我们从幅度中减去 1，而不是特殊大小写的负零。现在，-1 映射到 0x01，-2^63 也有非特殊情况表示（即 - 幅度 2^63 - 1，左移一位，设置 lsb / 符号位，所有位设置为 1） 。
因此，考虑 Zig Zag 编码的另一种方式是，它是一种更智能的符号和幅度表示：幅度左移一位，符号位存储在 lsb 中，并从负数的幅度中减去 1。
使用您发布的无条件按位运算符实现这些转换比显式测试符号、特殊情况操作负值（例如 - 取反并减 1，或按位不）、移动幅度，然后显式设置要快LSB 符号位。然而，它们实际上是等效的，并且这种更明确的符号和幅度系列步骤可能更容易理解我们正在做这些事情的内容和原因。
我会警告您，C / C++ 中的位移位有符号值是不可移植的，应该避免。左移负值具有未定义的行为，右移负值具有实现定义的行为。即使左移正整数也可能产生未定义的行为（例如，如果移入符号位，可能会导致陷阱或更糟糕的情况）。因此，一般来说，不要在 C / C++ 中对有符号类型进行位移位。“拒绝吧。”
首先转换为类型的无符号版本，以便根据标准获得安全、定义明确的结果。这确实意味着您不会进行负值的算术移位（即，将符号位向右拖动）——只有逻辑移位，因此您需要调整逻辑来解决这一问题。
以下是 C 语言中 2 的补码 64b 整数的锯齿形映射的安全且可移植的版本：
#include <stdint.h>
uint64_t zz_map( int64_t x )
{
return ( ( uint64_t ) x << 1 ) ^ -( ( uint64_t ) x >> 63 );
}
int64_t zz_unmap( uint64_t y )
{
return ( int64_t ) ( ( y >> 1 ) ^ -( y & 0x1 ) );
}
请注意 XOR 右侧项中符号位的算术否定。这会产生非负数 0 或负数全 1 —— 就像符号位从 MSB 到 LSB 的算术移位一样。然后，XOR 有效地“撤消”/“重做”负值的 2 的补码减 1（即 - 1 的补码或逻辑负），而无需任何条件逻辑或进一步的数学运算。