设置了 N 位的跳转值？

我们可以尝试按照其数值的顺序索引所有带有 N 1 的值。之后，我们可以计算起始数字的索引，将 100000 添加到其中，然后再次将索引转换为数字。

让我们用 N 1 （它是 ）调用 M 位值的数量。如果我们的数字在最高有效位中有 0，我们可以将其视为 （M-1） 位值。如果它的 MSB 为 1，我们可以计算前面有 N 位的数字（即 ），然后加上后面有 N 位的数字计数（这是 （N-1） 1 的 （M-1） 位数字的计数）。这使我们能够将 N1 的数字转换为其索引。f(M,N)N!/M!/(N-M)!100...00f(M-1,N)100...00

如果我没有错过任何东西，那么转换回来只是反转每一步。

复杂性如下所示。O(max-bit-count)

P.S. 听起来很复杂，希望有人能找到更简单的东西......

扩展 maxim1000 的答案：
如果是设置了 k 位的 n 位值的数量，则只是二项式系数。它可以计算为 ，极限为 （和 ）。C(n,k)CC(n,k) = C(n-1,k-1) * n / kC(n,0) = C(n,n) = 10 <= k <= n

从那里，您可以通过从最高有效到最不重要（从左到右）遍历其位来计算数字的索引。如果该数字总共有 n 位并设置了 k 位，则当遇到一个位集时，索引为 ，其中是该位的位置（0 是最低有效，n-1 是最有效的），如果取消设置该位，则为该数字的索引。请注意，如果两个数字设置了不同的位数，则它们可以具有相同的索引。C(bit_position, k) + subindexbit_positionsubindex

例如，有 10 个设置了 3 位的 5 位数字。在这里，它们以及它们的索引：

00111 - 0
01011 - 1
01101 - 2
01110 - 3
10011 - 4
10101 - 5
10110 - 6
11001 - 7
11010 - 8
11100 - 9

的索引是 6：
-- 第一个位集在位置 4，设置了 3 位，所以是 ;
-- 设置的第二个位位于位置 2，左边设置了 2 位，所以 ;
-- 设置的第三个位位于位置 1，还剩 1 位，所以 .
这使得.10110C(4,3)C(2,2)C(1,1)C(4,3) + C(2,2) + C(1,1) = 4 + 1 + 1 = 6

要从一个索引到相应的数字，你只需要做相反的操作：从值 0 开始，并设置对应于 a 的每个位，其中是一个已知常量，从 到 。C(p,k)kpn-10

然后，要跳转值，您可以转换获取数字的索引，添加到其中，然后转换回数字。jj

下面是一个实现：

auto binomial(uint64_t n, uint64_t k) -> uint64_t {
    if (k > n) {
        return 0;
    }
    if (k == 0 || k == n) {
        return 1;
    }

    // use the GCD to prevent overflow from `binomial(n-1, k-1) * n`
    uint64_t gcd = std::gcd(n, k);
    return binomial(n-1, k-1) / (k / gcd) * (n / gcd);

    // if you have access to a 128-bit type, you can also use that:
    // return binomial(n-1, k-1) * static_cast<__int128>(n) / k;
}

auto indexOf(uint64_t n, uint64_t bitCount) -> uint64_t {
    auto index = uint64_t(0);
    for (auto bit = 0; bit < 64; ++bit) {
        auto bitmask = uint64_t(1) << (63-bit);
        if ((n & bitmask) != 0) {
            index += binomial(63-bit, bitCount);
            --bitCount; // underflow doesn't matter here
        }
    }
    return index;
}

auto fromIndex(uint64_t index, uint64_t bitCount) -> uint64_t {
    auto n = uint64_t(0);
    for (auto bit = 0; bit < 64; ++bit) {
        auto b = binomial(63-bit, bitCount);
        if (b <= index) {
            auto bitmask = uint64_t(1) << (63-bit);
            n |= bitmask;
            index -= b;
            --bitCount; // underflow doesn't matter here
        }
    }
    return n;
}

auto bitCount(uint64_t n) -> unsigned int {
    auto count = 0u;
    while (n != 0) {
        if (n & 1 != 0) {
            ++count;
        }
        n >>= 1;
    }
    return count;
}

auto jumpOptimized(uint64_t n, uint64_t jumpLength) -> uint64_t {
    auto b = bitCount(n);
    auto index = indexOf(n, b);
    return fromIndex(index + jumpLength, b);
}

它可能会进一步优化，但希望这写得足够清楚，可以给你一个想法。

下面是一个使用 的朴素实现，用于针对优化的实现进行测试：std::next_permutation

auto jumpNaive(uint64_t n, uint64_t jumpLength) -> uint64_t {
    auto toBitVector = [](uint64_t n) -> std::vector<int> {
        auto v = std::vector<int>{};
        for (auto bit = 0; bit < 64; ++bit) {
            auto bitmask = uint64_t(1) << (63-bit);
            if ((n & bitmask) == 0) {
                v.push_back(0);
            } else {
                v.push_back(1);
            }
        }
        return v;
    };
    
    auto fromBitVector = [](std::vector<int> const& v) -> uint64_t {
        auto n = uint64_t(0);
        for (auto bit = 0; bit < 64; ++bit) {
            if (v[bit] == 1) {
                auto bitmask = uint64_t(1) << (63-bit);
                n |= bitmask;
            }
        }
        return n;
    };

    auto bitVector = toBitVector(n);
    for (auto i = uint64_t(0); i < jumpLength; ++i) {
        std::next_permutation(bitVector.begin(), bitVector.end());
    }
    return fromBitVector(bitVector);
}

你可以在这个完整的演示中尝试它们。