algorithm - 生成最短位序列base -2

Question

给定一个整数 X，其中 X 可以是负数或正数。在基数为-2 的系统中找到表示 X 的最短位序列。

在基数为 -2 的系统中，给定一个包含 N 位的数组 A，表示的整数为:A[i]*(-2 的幂 i) 之和，其中 i = 0..N-1

例子:

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

所以，给定 X = 18，算法应该返回 [0, 1, 1, 0, 1]

关于如何实现这种算法的任何想法.. 这样，给定一个整数 X 它返回表示该整数的最短位序列？

我想出的唯一方法是暴力搜索..从位 0 开始计算所有可能的总和，直到其中一个总和等于 X..这看起来不太好!

Answer 1

这不是一个完整的解决方案，但它可能会就如何进行提供一个好主意。

假设您的 base-negative-2 表示最多包含 N 个数字。它代表的数字范围是多少？

几个例子:

• 长度为 0 或更小:0
• 长度小于或等于 1:0 ... 1
• 长度小于或等于 2:-2 ... 1
• 长度 3 或更短:-2 ... 5
• 长度 4 或更短:-10 ... 5

您可能会注意到确定上述内容的递归规则；像这样:

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

为此，您甚至不需要“封闭”(在数学意义上)公式，只需一个递归实现即可。扩大范围，直到你的目标数字落在里面；然后生成您的表示。

顺便说一句，Wikipedia 中也有描述。 .