java - 编程 : Minimum steps required to convert a binary number to zero

Question

我当时正在做一个编程练习，一直想找出正确的算法。这是问题所在:

Given a decimal number, how many minimum possible steps are required to convert this to zero provided:

1. Change the bit i if the next bit i+1 is '1' and all the other bits i+2 and later are 0
2. Change the last bit without restriction

例如:

如果输入是 (8)Base10 = (1000)Base2，那么采取的步骤是:

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. 建立允许将前导 1 更改为 0 的情况。这意味着它后面应该跟一个 1，然后是全 0。为此写一个递归辅助算法。它将与主要算法非常相似，并且它们可能可以共享一些逻辑。
  2. 将 1 翻转为 0(1 步)
  3. 将剩余的 bits 位转换为 0。另一个递归调用。

该算法可能需要很长时间。它实际上是在计算步数，因此花费的时间与步数成正比，我认为这与输入数大致成正比。您的方法需要一个 long 参数，但是对于较大的 long 值，我的算法可能不会在其运行的计算机的生命周期内终止。此外，步数可能会溢出 int 甚至 long(如果输入是负的 long 值)。

快速方法

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

示例:输入 8 或 1000 二进制。结果 15 或 1111 二进制。模式是:结果的每一位是结果的前一位与输入中相同位置的位的异或。因此，从 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 的各种输入实现的上述第一个算法进行了对比，它们始终一致，因此我相信快速方法也是正确的。我仍然建议您编写代码、运行并测试它以验证我做对了。