c++ - 有没有办法将 Collat​​z 猜想优化为无分支算法？

Question

我正在尝试创建一个算法来计算 collat​​z 猜想，这是到目前为止的代码:

while (n > 1) {
   n % 2 == 0 ? n /= 2 : n = n * 3 + 1;
}

我想知道是否有办法进一步优化它，因为效率和速度对此至关重要，并且我听说过无分支编程，但我不确定如何实现它，或者是否值得开始于。

Answer 1

当然。当然，您需要循环，但内部的工作可以这样完成:

n /= (n&-n);  // remove all trailing 0s
while(n > 1) {
    n = 3*n+1;
    n /= (n&-n);  // remove all trailing 0s
}

此技术同时将所有除以 2 的操作也很有帮助，而不需要对每个除法进行单独的迭代。