some functions to get the stopping time of a number in the collatz conjecture

collatz.hpp

#ifndef SAM_B_COLLATZ_CONJECTURE_HEADER
#define SAM_B_COLLATZ_CONJECTURE_HEADER 1

#include <cstdint>
#include <bitset>
#include <bit>

namespace collatz
{
    using size_t = std::intmax_t;
    using uint_t = std::uintmax_t;

    constexpr size_t iterations(uint_t n) noexcept
    {
        size_t count = std::countr_zero(n);
        n >>= count;

        while (n != uint_t(1))
        {
            n += n >> 1;
            ++n;

            const size_t tz = std::countr_zero(n);
            n >>= tz;

            count += 2;
            count += tz;
        }

        return count;
    }

    constexpr uint_t maximum(uint_t n) noexcept
    {
        uint_t max = n;
        n >>= std::countr_zero(n);

        while (n != uint_t(1))
        {
            n = uint_t(3) * n + uint_t(1);
            if (max < n)
                max = n;

            n >>= std::countr_zero(n);
        }

        return max;
    }

    constexpr size_t MAX_BITSET_SIZE = 0x1000000;

    // use std::bitset to get arbitrary precision for counting iterations
    template <size_t B, bool SAFE = B <= MAX_BITSET_SIZE>
    constexpr size_t iterations_slow(std::bitset<B> n) noexcept
    {
        // figure out what the maximum bit in the set is
        // this is basically so we don't waste cycles
        // looping over the same bits over and over again
        size_t max_bit = B - 1;
        for (; max_bit && !n.test(max_bit); --max_bit)
            ;

        // variable to count number of iterations
        size_t count = 0;

        // divide by 2 as much as possible
        while (!n.test(count))
            ++count;
        n >>= count;
        max_bit -= count;

        // while the number is not equal to 1 basically
        while (max_bit > 0)
        {
            // check to see if bitset will overflow
            if constexpr (SAFE)
            {
                if (max_bit >= B - 1)
                {
                    std::bitset<2 * B> cast;
                    for (size_t bit = 0; bit < B; ++bit)
                        if (n.test(bit))
                            cast.set(bit);

                    return count + iterations_slow<2 * B>(cast);
                }
            }

            // this adds a half to itself, which is 2 steps in one
            count += 2;
            bool a = n.test(0), c = false;
            for (size_t bit = 0; bit <= max_bit; ++bit)
            {
                const bool b = n.test(bit + 1);
                const bool r = a ^ b;
                n.set(bit, r ^ c);
                c &= r;
                c |= a & b;
                a = b;
            }

            if (c)
                n.set(++max_bit);

            // this basically checks how many times you would
            // divide by 2 if you were to add 1 to the number
            if (n.test(0))
            {
                // count number of 1's starting from right side
                // these will all flip over to 0 when you add 1
                size_t rones = 1;
                while (n.test(rones))
                    ++rones;

                count += rones;
                max_bit -= rones;
                n >>= rones;
            }

            // the number is always even in this stage,
            // so this adds 1 to the number
            n.set(0);
        }

        return count;
    }
}

#endif