有一种模式可以让您了解恒定时间的最佳下一步。实际上，在某些情况下可能存在两个同样最佳的选择-在这种情况下，可以在恒定时间内得出其中一个。

如果查看 n 的二进制表示形式及其最低有效位，则可以得出有关哪种操作导致解决方案的结论。简而言之：

• 如果最低有效位为零，则除以2
• 如果 n 为3，或2个最低有效位为01，则减去
• 在所有其他情况下：添加。

证明

如果最低有效位为零，则下一个操作应为2的除法。我们可以尝试先进行2次加法再除法，但是可以通过两个步骤来实现相同的结果：除法和加法。同样减去2。当然，我们可以忽略无用的后续加减步骤（反之亦然）。因此，如果最后一位为0，则除法是必须的。

那么其余的3位模式就像**1。有四个。让我们来写a011一个数字，该数字以位结尾011并具有一组前缀位，这些位代表值 a ：

• a001：添加一个将给出a010，然后应该进行除法a01：：进行了2个步骤。我们现在不想减去一个，因为这将导致a00，我们从开始就可以分两步得出（减去1并除以）。因此，我们再次加和除以获得get a1，并且出于相同的原因，我们再次重复该操作，得到：a+1。这花了6步，但得出的数字可以5步得出（减1，除3乘，加1），所以很明显，我们不应该执行加法。减法总是更好。

• a111：加法等于或好于减法。在4个步骤中，我们得到a+1。减法和除法会给a11。与初始加法路径相比，现在加法效率低下，因此我们将这种减法/除法重复两次，并分a6步进行。如果a以0结尾，那么我们可以分5个步骤完成（加，除三遍，减法），如果a以1结尾，那么偶数为4。所以加法始终更好。

• a101：减法和双重除法导致a13个步骤。加法和除法导致a11。与减法路径相比，现在减法和除法效率低下，因此我们将加法和除法两次以得到a+15步。但是通过减法路径，我们可以分4个步骤来实现。所以减法总是更好。

• a011：加法和双重除法导致a1。要获得a，还需要再执行2步（5），而要获得a+1：还需要再执行6个步骤。减法，除法，减法，双除法导致a（5），要得到则a+1需要再执行一步（6）。因此加法至少与减法一样好。但是，有一种情况不容忽视：如果 a 为0，则减法路径将以2步的一半到达解的中点，而加法路径则需要3步。因此，加法总是导致求解，除非当 n 为3时：然后应选择减法。

因此，对于奇数，倒数第二个位决定下一步（3除外）。

Python代码

这导致以下算法（Python），该算法每个步骤都需要迭代一次，因此应具有 O（logn） 复杂度：

def stepCount(n):
    count = 0
    while n > 1:
        if n % 2 == 0:             # bitmask: *0
            n = n // 2
        elif n == 3 or n % 4 == 1: # bitmask: 01
            n = n - 1
        else:                      # bitmask: 11
            n = n + 1
        count += 1
    return count

看到它在repl.it上运行。

JavaScript片段

这是一个您可以输入 n 值并让代码段生成步骤数的版本：

function stepCount(n) {

    var count = 0

    while (n > 1) {

        if (n % 2 == 0)                // bitmask: *0

            n = n / 2

        else if (n == 3 || n % 4 == 1) // bitmask: 01

            n = n - 1

        else                           // bitmask: 11

            n = n + 1

        count += 1

    }

    return count

}



// I/O

var input = document.getElementById('input')

var output = document.getElementById('output')

var calc = document.getElementById('calc')



calc.onclick = function () {

  var n = +input.value

  if (n > 9007199254740991) { // 2^53-1

    alert('Number too large for JavaScript')

  } else {

    var res = stepCount(n)

    output.textContent = res

  }

}


<input id="input" value="123549811245">

<button id="calc">Caluclate steps</button><br>

Result: <span id="output"></span>

请注意，JavaScript的精度限于10 16左右，因此对于较大的数字，结果将是错误的。请改用Python脚本以获得准确的结果。