标签: bitfoo

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

给定两个字节,如何在两个字节的开头找到公共位的长度.

例如:

9 == 00001001
6 == 00000110

Common prefix is 0000, length 4

我在C#工作,所以请坚持使用C#操作.

附录:这段特殊的代码将运行数千次,并且需要非常快.