如何否定-2号基数？

最近我接受了Codility测试，我想知道如何否定-2基数 ？

例如，数组[1,0,0,1,1]代表基数-2中的 9 ：

 -2 bases: 1,-2,4,-8,16 1 + (-8) + 16 = 9 [1,0,0,1,1] 

基数为-2的负9为：

 -2 bases: 1,-2,4,-8 1 + (-2) + -8 = -9 [1,1,0,1] 

我对这个问题一无所知。 必须有一些直观的解决方案。 你有什么提示吗？

Answer 1

在基数-2中，位置i处的1表示（-2） ⁱ 。

因此，位置[ i ， i + 1]中的[1,1]表示（-2） ⁱ +（ – 2） ^{i + 1} =（ – 2） ⁱ +（-2）（ – 2） ⁱ =（1 + -2）（ – 2） ⁱ = – （ – 2） ⁱ 。

因此，您可以通过将其更改为[1,1]来否定任何[1,0]的出现，反之亦然。

当然，任何其他出现的0都可以保持不变：-0 = 0。

所以在你的例子中，我们将[1,0,0,1,1]分成[{1,0}，{0}，{1,1}]，否定每个部分得到[{1,1}，{ 0}，{1,0}]，即[1,1,0,1,0]，并删除不必要的高0，产生[1,1,0,1]。

Answer 2

我们来试试几个例子：

  (16 -8 4 -2 1) 1 = 0 0 0 0 1 -1 = 0 0 0 1 1 2 = 0 0 1 1 0 -2 = 0 0 0 1 0 3 = 0 0 1 1 1 -3 = 0 1 1 0 1 4 = 0 0 1 0 0 -4 = 0 1 1 0 0 5 = 0 0 1 0 1 -5 = 0 1 1 1 1 

我们可以尝试用数学方法定义它：

给定输入I（b）（其中B是位数），

1. I =Σ（-2） ^b I（b） – 基数-2的定义）
2. O = -I – 我们正在努力解决的问题
3. O =-Σ（-2） ^b I（b） – 取代
4. O =Σ – （ – 2） ^b I（b） – 分布
5. – （ – 2） ^b =（ – 2） ^b +（ – 2） ^{b + 1}
6. O =Σ（（ – 2） ^b +（ – 2） ^{b + 1} ）I（b） – 取代
7. O =Σ（（ – 2） ^b I（b）+（ – 2） ^{b + 1} I（b）） – 置换
8. O =Σ（-2） ^b I（b）+Σ（-2） ^{b + 1} I（b）
9. O（b）= I（b）+ I（b-1）

现在，这留下了O（b）为0,1或2的可能性，因为I（b）总是0或1。

如果O（b）是2，那就是“进位”，让我们看几个进位的例子：

  (16 -8 4 -2 1) (16 -8 4 -2 1) 1+1 = 0 0 0 0 2 = 0 0 1 1 0 -2-2 = 0 0 0 2 0 = 0 1 1 0 0 4+4 = 0 0 2 0 0 = 1 1 0 0 0 

对于每个b，从0开始，如果O（b）> = 2，则从O（b）中减去2并增加O（b + 1）和O（b + 2）。 这样做直到达到最大B.

希望这足以详细解释它。