algorithm - 最短位序列逻辑

Question

我想了解最短位序列是如何工作的。我的意思是逻辑。我需要为它创建一个程序，但实际上并不知道这个最短的位序列是什么。我试图谷歌但徒劳无功。我遇到了这个 Question在 SO 上，但我无法从中理解任何内容。任何人都可以向我解释一下或指导我到可以理解其背后逻辑的地方吗？

Answer 1

正如 Jan Dvorak 在评论中指出的那样，它只是一个以 -2 为基数的数字。

考虑您的示例 [0, 1, 1, 1, 1, 1, 1]。

-2 的指数与 2 相同，但符号交替:

(-2)^0 =   1
(-2)^1 =  -2
(-2)^2 =   4
(-2)^3 =  -8
(-2)^4 =  16
(-2)^5 = -32
(-2)^6 =  64
 ...

在位序列表示法中，最低的指数在前，即顺序与普通二进制数相反。

[0, 1, 1, 1, 1, 1, 1] = 0 * (-2)^0  +
                        1 * (-2)^1  +
                        1 * (-2)^2  +
                        1 * (-2)^3  +
                        1 * (-2)^4  +
                        1 * (-2)^5  +
                        1 * (-2)^6

它给出(从下往上)

[0, 1, 1, 1, 1, 1, 1] = 64 - 32 + 16 - 8 + 4 - 2 = 42