编程：将二进制数转换为零所需的最小步骤

Question

正在进行编程练习，并坚持找出正确的算法。这是问题所在：

给定十进制数，将此转换为零所需的最小步数为：

1. 如果下一位i + 1为'1'则更改位i，并将所有其他位i + 2和更高位置为0
2. 无限制地更改最后一位

例如： 如果输入是（8）基数10 =（1000）基数2，那么采取的步骤是：

1000→1001→1011→1010→1110→1111→1101→1100→0100→0101→0111→0110→0010→0011→0001→0000

总共需要15个步骤。

完成以下定义：

int minStepsRequired(long number)

获得伪代码或算法是可以的。这不是作业或作业。

Answer 1

对于递归算法来说，这是一个很好的问题。

如果二进制表示的长度为0，则您已经可以说出答案。或者如果不允许长度为0，那么如果长度为1，则根据该位是0还是1来说明答案。

如果长度超过1：

• 如果第一位为0，则答案与没有该0位时的答案相同。删除它并递归调用以获得答案。
• 如果第一位为1，则分为三个子问题并找到每个子问题的步数： 建立允许您将前导1更改为0的情况。这意味着它应该后跟1然后全部为0。为此编写递归辅助算法。它将与主算法非常相似，并且可能共享一些逻辑。 翻转1到0（1步） 将剩余的位转换为0.另一个递归调用。

该算法可能需要很长时间。它实际上是计算步数，所以需要时间与步数成比例，我认为步数大致与输入数成正比。你的方法采用long参数，但是对于大long值的算法，它可能无法在运行它的计算机的生命周期内终止。步数也可能溢出int甚至long（如果输入是负long值）。

快乐的编码。如果那是我，我会实际编码并运行它来验证我是否正确。

快捷的方式

以下解决方案不需要递归并在恒定时间内运行。我无法正确解释它是如何工作的，如果我们想将它用于某些事情，这是一个严重的问题。我玩了一些例子，看到了一个模式并概括了它。相比之下，恕我直言，上面的递归解决方案的一些优点是它很容易理解（如果你理解递归）。

示例：输入8或1000二进制。结果15或1111二进制。模式是：结果的每个位是结果的前一位的XOR和输入中相同位置的位。因此，从1000只需复制前位，1。以下位是1 XOR 0 = 1，其中1是结果的前位，0是从输入中获取的。剩余的两位以相同的方式计算。

一个较长的例子，你可以检查你是否理解：

Input:  115 = 1110011
Result:       1011101 = 93

或者在代码中：

static BigInteger calculateStepsRequired(long number) {
    // Take sign bit
    int bit = number < 0 ? 1 : 0;
    BigInteger result = BigInteger.valueOf(bit);
    for (int i = 0; i < 63; i++) {
        number = number << 1;
        int sign = number < 0 ? 1 : 0;
        bit = (bit + sign) % 2;
        result = result.shiftLeft(1).add(BigInteger.valueOf(bit));
    }
    return result;
}

我已经使用高达100 000 000的各种输入检查了我自己实现上面第一个算法的方法，并且他们总是同意，所以我认为快速方法也是正确的。

Answer 2

起初，我尝试使用递归深度优先函数（在NodeJS中）解决它，但它只适用于小数字 - 由于堆栈中递归调用的数量，输入值（如10^5）会生成运行时错误。

那么我试着看看如何将问题减少到较小问题的总和，并发现N的步数为N，即2的幂，是

规则1

N * 2 - 1

（例如：2的步数为3，32为63，256为511，依此类推）。

然后我找到了如何处理任何其他数字（这不是2的幂），因为任何整数是2的不同幂的总和（因此二进制表示），我只需要看看步数是否会加起来......但事实并非如此。但是，我确实发现我不仅要从每个2的幂增加步数，而且还要

规则＃2

从最高位数开始，以备用方式减去并添加步骤

Demonstration

给定数字42（101010二进制）

让我们首先应用规则＃1

1 0 1 0 1 0
^ ^ ^ ^ ^ ^
| | | | | |_           0 steps
| | | | |___  2*2-1 =  3 steps
| | | |_____           0 steps
| | |_______  2*8-1 = 15 steps
| |_________           0 steps
|___________ 2*32-1 = 63 steps

其次，应用规则＃2：

63 - 15 + 3 = 51

总步数为51