algorithm - 最短位序列逻辑

Question

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

Answer 1

正如 Jan Dvorak 在评论中指出的那样，它只是一个用 base 编写的数字-2。

考虑你的例子[0, 1, 1, 1, 1, 1, 1]。

的指数与-22 相同，但符号交替：

(-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

Answer 2

def solution(A):
    n=len(A)
    result=0
    if n==0:
        return -1
    for i in range(n):
        result+=(A[i]*pow(-2,i))
    return result
print solution([1,0,0,1,1])