有没有办法将 Collatz 猜想优化为无分支算法？

Question

我正在尝试创建一个算法来计算 collatz 猜想，这是目前的代码：

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，而不是每次都需要单独迭代，这也很有帮助。

Answer 2

使其无分支（循环条件除外）的一种方法是将 n / 2 与 n % 2 == 0 结果相乘（1 为 true）并乘以 (n * 3 + 1) 与 (n % 2 == 0) 的取反结果相加。

void collatz(unsigned long long n) {
    std::cout << n << '\n';
    while (n > 1) {
        auto m = n % 2 == 0;
        n = m * (n / 2) + !m * (n * 3 + 1);
        std::cout << n << '\n';
    }
}

Demo

有没有办法将 Collatz 猜想优化为无分支算法？

Is there a way to optimise the Collatz conjecture into a branchless algorithm?

c++

collatz

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

Is there a way to optimise the Collatz conjecture into a branchless algorithm?

c++

collatz

有没有办法将 Collatz 猜想优化为无分支算法？