Shortest Bit Sequence Logic

Question

I am trying to understand how the shortest bit sequence works. I mean the logic. I need to create a program for him, but I don’t know what this shortest sequence of bits is. I tried to make Google, but in vain. I came across this Question , but I can’t understand anything. Can someone explain this to me or guide me somewhere where I can understand the logic of this?

Answer 1

As Jan Dvorak noted in the comments, this is just a number written in the -2 database.

Consider your example [0, 1, 1, 1, 1, 1, 1] .

Indicators -2 are the same as for 2, but with variable signs:

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

In the notation of a sequence of bits, the first exponentials appear in the first place, that is, the order is reversed compared to ordinary binary numbers.

 [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 

which gives (bottom to top)

 [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])