Jump values of N bits set?

I want the next + 100,000 value of a number with N bits, given that the resulting value must have N bits as well.

So, for example : 30 is 0b11110

and the next value is 39 0b100111;

I read that links and got a way to find the next value with N bits.

Now, is there a way to "jump" 100,000 values at once?

100,000 is arbitrary here, it could be -much- higher.

The only way I can think of is to make my jump from my initial value, count the number of bits of the new value and adjust that new value at the bit level to my desired N bits. That's a very manual process and I would like to know if a more efficient algorithm exists. But it gives me no guarantees on the number of values jumped.

Solution

To expand on maxim1000's answer:
if C(n,k) is the number of n-bit values with k bits set, then C is just the binomial coefficient. It can be computed as C(n,k) = C(n-1,k-1) * n / k, with the limit being C(n,0) = C(n,n) = 1 (and 0 <= k <= n).

From there, you can compute a number's index by iterating through its bits from most significant to least significant (left to right). If the number has n bits total and k bits set, then, when encountering a bit set, the index is C(bit_position, k) + subindex, where bit_position is the bit's position (0 is the least significant, n-1 the most significant), and subindex is the index of the number if you unset that bit. Note that two numbers can have the same index if they have a different number of bits set.

For example, there are 10 5-bit numbers with 3 bits set. Here they are, along with their indices:

The index of 10110 is 6:
-- the first bit set is in position 4, with 3 bits set, so that's C(4,3);
-- the second bit set is in position 2, with 2 bits set left, so C(2,2);
-- the third bit set is in position 1, with 1 bit set left, so C(1,1).
That makes C(4,3) + C(2,2) + C(1,1) = 4 + 1 + 1 = 6.

To go from an index to the corresponding number, you just need to do the reverse: start with a value of 0 and set each of the bits that correspond to a C(p,k), where k is a known constant and p goes from n-1 to 0.

Then, to jump j values ahead, you can convert take the number's index, add j to it, and convert back to a number.

Here is an implementation:

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);
}

It can probably be optimized further, but hopefully this is written clearly enough to give you the idea.

Here is a naive implementation using std::next_permutation, to test against the optimized implementation:

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);
}

And you can try both of them in this complete demo.