protocol-buffers - Google Protocol Buffer :ZigZag编码

Question

来自Encoding - Protocol Buffers - Google Code上的“签名类型”:

ZigZag encoding maps signed integers to unsigned integers so that numbers with a small absolute value (for instance, -1) have a small varint encoded value too. It does this in a way that "zig-zags" back and forth through the positive and negative integers, so that -1 is encoded as 1, 1 is encoded as 2, -2 is encoded as 3, and so on, as you can see in the following table:

Signed Original  Encoded As
0                0
-1               1
1                2
-2               3
2147483647       4294967294
-2147483648      4294967295

In other words, each value n is encoded using

(n << 1) ^ (n >> 31)

for sint32s, or

(n << 1) ^ (n >> 63)

for the 64-bit version.

(n << 1) ^ (n >> 31)如何等于表中的内容？我知道这对肯定有用，但是对于-1来说如何工作？ -1不是 1111 1111，而 (n << 1)是 1111 1110吗？ (是否可以在任何语言中对否定词进行位移位？)

尽管如此，使用公式并执行 (-1 << 1) ^ (-1 >> 31)，假设int为32位，我得到的 1111 1111为40亿，而表格认为我应该有1。

Answer 1

向右移动负号整数将复制符号位，以便

(-1 >> 31) == -1

然后，

(-1 << 1) ^ (-1 >> 31) = -2 ^ -1
                       = 1

这可能更容易以二进制形式显示(此处为8位):

(-1 << 1) ^ (-1 >> 7) = 11111110 ^ 11111111
                      = 00000001