标签: zigzag-encoding

在谷歌协议缓冲区编码概述中,他们引入了一种称为"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位整数

来自编码的 "签名类型" - 协议缓冲区 - Google代码:

ZigZag编码将有符号整数映射到无符号整数,因此具有较小绝对值(例如,-1)的数字也具有较小的varint编码值.它通过正负整数来回"zig-zags"的方式做到这一点,因此-1被编码为1,1被编码为2,-2被编码为3,依此类推,就像你一样可以在下表中看到:

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

Run Code Online (Sandbox Code Playgroud)

换句话说,使用编码每个值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.

ZigZag需要大量的开销才能写入/读取数字.实际上我惊呆了,看到它不仅仅是按原样写入int/long值,而是进行了大量额外的加扰.甚至还有一个循环:https: //github.com/mardambey/mypipe/blob/master/avro/lang/java/avro/src/main/java/org/apache/avro/io/DirectBinaryEncoder.java#L90

我似乎无法在Protocol Buffers文档或Avro文档中找到,或者说我自己,那些扰乱数字的优势是什么？为什么在编码后交替使用正数和负数会更好？

为什么他们不只是用little-endian,big-endian,网络顺序编写,只需要将它们读入内存并可能反转位字节序？我们用性能支付什么？

我正在使用Dart对32位整数进行ZigZag编码.这是我正在使用的源代码:

int _encodeZigZag(int instance) => (instance << 1) ^ (instance >> 31);
int _decodeZigZag(int instance) => (instance >> 1) ^ (-(instance & 1));

代码在DartVM中按预期工作.

但是在dart2js中,_decodeZigZag如果输入负数,则函数返回无效结果.例如-10.-10被编码19并应该被解码回来-10,但它被解码为4294967286.如果我(instance >> 1) ^ (-(instance & 1))在Chrome的JavaScript控制台中运行,我会得到预期的结果-10.对我来说,这意味着Javascript应该能够使用数字模型正确运行此操作.

但是Dart2Js生成以下JavaScript,它看起来与我在控制台中测试的代码不同:

return ($.JSNumber_methods.$shr(instance, 1) ^ -(instance & 1)) >>> 0;

为什么Dart2Js将函数的右移0加到函数中？没有转变,结果将如预期的那样.

现在我想知道,这是Dart2Js编译器中的错误还是预期的结果？有没有办法强制Dart2Js输出正确的JavaScript代码？

或者我的Dart代码错了？

PS:还测试了将XOR分成其他操作,但是Dart2Js仍在添加正确的移位:

final a = -(instance & 1);
final b = (instance >> 1);

return (a & -b) …