问题标签 [zigzag-encoding]

在 google protocol buffers encoding overview中，他们引入了一种称为“Zig Zag Encoding”的东西，它采用小幅度的有符号数字，并创建一系列小幅度的无符号数字。

例如

等等。他们为此提供的编码功能相当聪明，它是：

我了解它是如何工作的，但是，我终其一生都无法弄清楚如何将其反转并将其解码回有符号的 32 位整数

来自编码上的“签名类型” -协议缓冲区-谷歌代码：

ZigZag 编码将有符号整数映射到无符号整数，因此具有较小绝对值（例如 -1）的数字也具有较小的 varint 编码值。它以一种通过正整数和负整数来回“曲折”的方式来执行此操作，因此 -1 被编码为 1，1 被编码为 2，-2 被编码为 3，依此类推，就像你可以在下表中看到：

换句话说，每个值 n 使用编码

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

对于 sint32s，或

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

对于 64 位版本。

表中(n << 1) ^ (n >> 31)的等于什么？我知道这对积极因素有用，但是对于-1来说，这如何工作？不会 -11111 1111和(n << 1)是1111 1110吗？（在任何语言中，对负数的移位是否格式正确？）

尽管如此，使用公式并做(-1 << 1) ^ (-1 >> 31)，假设一个 32 位整数，我得到1111 111140 亿，而表格认为我应该有 1。

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

代码在 DartVM 中按预期工作。

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

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

为什么 Dart2Js 会在函数中添加一个使用过的右移 0？如果没有转变，结果将如预期的那样。

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

还是我的 Dart 代码错了？

PS：还测试了将 XOR 拆分为其他操作，但 Dart2Js 仍在添加右移：

结果是：

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 文档中找到，或者自己推理，这样的加扰数字有什么好处？为什么编码后交替正负数更好？

为什么它们不只是以小端、大端、网络顺序编写的，只需要将它们读入内存并可能反转位字节序？我们用性能买什么？

我正在尝试创建一个正整数和负整数数组，代表一个位置的南北距离-我需要以之字形顺序查看数组的元素。

这意味着最大的成员首先出现，最小的成员出现在第二位，其余元素在较大的成员从最大减少和较小的成员从最小增加之间交替出现。

即数组 [1, 3, 6, 9, -3] 变为 [9, -3, 6, 1, 3]。

我正在尝试完成这个函数wiggleArrangeArray，它接受一个参数，一个由 n 个整数组成的整数数组。

所需的输入格式、约束和输出格式

我不知道怎么说

“如果数组中的项大于数组中的其他项，则先显示。”

“如果该项目小于数组中的其他项目，则显示第二个。”

“然后在下一个最大的数字和下一个最小的数字之间交替”

如果可能，请提供帮助。这是 C++ 解决方案的链接，但我在 Python 中需要它。谢谢。

编辑：该功能需要与以下测试一起使用：

我想以这种方式对张量单元进行排序

请注意，每个单元格不是单个值，而是一堆值（DCT 组件）。所以，原始张量的维度不是二维的。

我设计了一个（相当简单的）网络协议，它严重依赖于VLQ 编码的整数和之字形编码（如Protobuf所述）。我在互联网上了解到这些技术，我觉得它们很明显。但是，现在我想撰写一份 Internet-Draft 来描述我的协议，而在规范性文档中引用 Wikipedia 文章似乎很荒谬。

有人知道一个知名的出版物，描述 VLQ 和 zig-zag 编码吗？他们的原始发明者是谁？

我正在寻找一些可以提供函数的库，这些函数可以帮助将 zig-zag 编码的字节数组解码为 2 的补码long/int并返回。

由于在protobuf中使用了 ZigZag，我希望 guava 有它的功能，但谷歌搜索并没有给出任何结果。通过 ZigZag 编码，我的意思是：

我必须“重新发明轮子”吗？