“隐藏在黑暗中的钥匙啊，在我面前显示你真正的力量吧，现在以你的主人黑猫之名，封印解除——“ 黑猫最近在研究编码——隐藏在计算机软硬件背后的语言，他发现有一种数值压缩的编码方法被称为Varint方法，这种方法可以理解成，是用多个较小的数据去表示一个较大的数据，在网络传输中常常用到这种方法，以实现将一个大文件拆分成多个较小的文件传输，传输后对方再使用多个较小的文件还原出这个较
“隐藏在黑暗中的钥匙啊，在我面前显示你真正的力量吧，现在以你的主人黑猫之名，封印解除——“ 黑猫最近在研究编码——隐藏在计算机软硬件背后的语言。他发现有一种数值压缩的编码方法被称为Varint方法。这种方法可以理解成，是用多个较小的数据去表示一个较大的数据。在网络传输中常常用到这种方法，以实现将一个大文件拆分成多个较小的文件传输，传输后对方再使用多个较小的文件还原出这个较大的文件。 首先，我们来复习一下二进制下如何编码一个无符号整数x，考虑x的二进制表示x=a0∗20+a1∗21+...+ak−1∗2k−1x = a_0 * 2^0 + a_1 * 2^1 + ... + a_{k-1} * 2^{k-1}x=a0∗20+a1∗21+...+ak−1∗2k−1，其中k-1表示的是最高位，如果x=0的话，那么k=1。 如果把一个较大的数字x，拆成多个较小的数字表示，以方便分段发送的话，将其拆成二进制，一位一位发出是最容易想到的。但是这样一方面，每一段太小，影响了发送效率；另一方面，当有多个较大的数字x1、x2…xn一起发送的话，还需要使用标记位来标记以分割x1、x2…xn。 现在，对于一个较大的数字x（其二进制有k位），黑猫想要使用m=⌈k/7⌉m = lceil{k/7} rceilm=⌈k/7⌉个较小的数字（每个较小的数字的二进制表示有8位，即就是使用无符号数原码表示的话取值范围为[0,255]）来表示x，也就是说x被表示成x=b0b1b2..bm−1x = b_0b_1b_2..b_{m-1}x=b0b1b2..bm−1。为了避免使用标记位，我们约定，对于b0b1b2..bm−2b_0b_1b_2..b_{m-2}b0b1b2..bm−2来说，他们的最高位的比特一定被设置为1，而bm−1b_{m-1}bm−1的最高位一定被设置为0，所以虽然每个较小的数组都使用了8位二进制表示，但是我们只能使用其中的7位，最高位是不会被使用的。这样的话，只是用一个较小的数字来表示x的话，x可以被表示的范围为[0,127],使用两个较小的数据表示x的话，x可以被表示的范围为[128,214−1][128,2^{14}-1][128,214−1]，以此类推，一直可以被表示到264−12^{64}-1264−1。我们可以理解成，把x的二进制表示，每七位压缩成了一位b(使$b⌊i/7⌋b_{lfloor i / 7 rfloor}b⌊i/7⌋来表示ai−6ai−5...aia_{i-6}a_{i-5}...a_{i}ai−6ai−5...ai），因此，不难得出由多个较小数字b还原回x的公式为: x=(b0−128)∗20+(b1−128)∗27+(b2−128)∗214+...+(bm−2−128)∗27(m−2)+bm−1∗27(m−1)x = ( b_0 - 128 ) * 2^0 + ( b_1 - 128 ) * 2^7 + (b2 - 128 ) * 2^{14} + ... + ( b_{m-2} - 128 ) * 2^{7(m-2)} + b_{m-1} * 2^{7(m-1)}x=(b0−128)∗20+(b1−128)∗27+(b2−128)∗214+...+(bm−2−128)∗27(m−2)+bm−1∗27(m−1) 在这个公式中，我们对b0b1b2....bm−2b_0b_1b_2....b_{m-2}b0b1b2....bm−2都减去了128，是因为我们人为的把这些位的最高位都设置成了1。(128的二进制表示为1000 0000)。 例如，对于数字7来说，将被用一位b0 = 7 来表示，而对于数字260，则将被使用两位：b0 = 132 , b1 = 2 来表示。 为了在传输中避免考虑符号问题，接下来我们将使用ZigZag编码，使其可以使用无符号数表示有符号数。这种编码可以被看做是一种有符号数向无符号数的映射。将有符号数0，用无符号数0表示，有符号数-1用无符号1表示，有符号数1用无符号数2表示，有符号-2用无符号3表示，有符号数2用无符号数4表示，以此类推。简单地说，对于x ≥ 0来说，有符号数x将被映射为无符号数2x,对于x < 0来说，有符号数x将被映射到 -2x - 1 上。 例如，75使用Zigzag编码，将变为150，再使用Varint编码为b0 = 150 , b1 = 1 , 而 -75将被编码为149，再被进一步编码为b0 = 149 , b1 =1 。 在这个问题中，我们仅考虑映射前的数据范围为[−263,263−1][ -2^{63} , 2^{63} - 1 ][−263,263−1]。 现在，黑猫看了这么大一堆的题目以后，整个人都变成mobier了，所以需要你帮他解决一些问题: 给出一个数字序列，是使用有符号整数进行ZigZag编码后，再进行Varints编码后传输给你的结果。黑猫需要你帮他计算出原来的数列是多少？
标签： HBC15889编码的奥秘题解
