Generate shortest bit sequence base -2

Given an integer X where X can be negative or positive. find the shortest bit sequence that represent X in a base -2 system.

In a base -2 system, given an array A of N bits, the represented integer is: sum of A[i]*(-2 power i) for i = 0..N-1

example:

[1,0,1] = 5
[1,0,0,1] = -7
[1,0,0,1,0,1] = -39

so, given X = 18 the algorithm should return [0, 1, 1, 0, 1]

any idea on how to implement such an algorithm.. such that, given an integer X it returns the shortest bit sequence that represent that integer ?

The only thing that I came up with is brute force search.. starting at bit 0 and calculating all possible sums until one of the sums is equal to X.. which does not look nice!

1 Answer

This is not a full solution, but it will probably give a good idea on how to proceed.

Suppose your base-negative-2 representation contains at most N numbers. What would be the range of numbers it represents?

A few examples:

• length 0 or less: 0
• length 1 or less: 0 ... 1
• length 2 or less: -2 ... 1
• length 3 or less: -2 ... 5
• length 4 or less: -10 ... 5

You probably can notice the recursive rule that determines the above; something like this:

Extend the range by adding or subtracting 2^n-1 to the appropriate end of the earlier range

You don't even need a "closed" (in a mathematical sense) formula for this, just a recursive implementation. Extend the range until your target numbers falls inside; then generate your representation.

BTW it's also described in Wikipedia.