只有某些位可以改变的二进制数的所有组合

Question

我想知道是否有一种算法可以生成二进制数所有可能的组合，其中只有某些位置的位可以改变，例如我们有以下位流，但只有位置标记的位x可以改变（这个例子有8个地方可以改变做不同的组合，一共2^8）：

x00x0000x000000x00x00x000x000x

一个解决方案是首先将数字视为 8 位数字，然后只计算 xxxxxxxx 的所有组合。但是，这并不能完全满足我的需求，因为我想稍后在线性移位寄存器 (LFSR) 中使用数字，目前，我正在寻找一个利用 std::bitset.[=14= 的答案]

Answer 1

像这样

// sample indexes
static const int indexes[8] = { 0, 4, 8, 11, 13, 16, 22, 25 };

std::bitset<32> clear_bit_n(std::bitset<32> number, int n)
{
    return number.reset(indexes[n]);
}

std::bitset<32> set_bit_n(std::bitset<32> number, int n)
{
    return number.set(indexes[n]);
}

void all_combinations(std::bitset<32> number, int n)
{
    if (n == 8)
    {
        // do something with number
    }
    else
    {
        all_combinations(clear_bit_n(number, n), n + 1);
        all_combinations(set_bit_n(number, n), n + 1);
    }
}

all_combinations(std::bitset<32>(), 0);

Answer 2

可以通过使用“掩码增量”进行迭代来枚举满足该模式的整数，这会增加可变位但保持固定位不变。为方便起见，我将假设“固定位”为零，但如果不是，它仍然可以进行较小的更改。 mask固定位为1，可变位为0。

uint32_t x = 0;
do {
    // use x
    ...
    // masked increment
    x = (x | mask) + 1 & ~mask;
} while (x != 0);

x | mask 设置固定位，以便进位将“通过”固定位。 +1 增加变量位。 &~mask 清除已设置的额外位，将固定位变回零。

std::bitset不能递增，所以很难直接使用，但必要时可以将整数转换为std::bitset。

Answer 3

那么，答案已经有了。但只是转储代码，没有任何解释。不好。不确定，为什么你接受了。无论如何...

我想用不同的方法添加一个答案，并解释一下步骤。

基本上，如果你想要一个二进制数的所有组合，那么你可以简单地“计数”或“加一”。 3 位值的示例。这将是十进制 0、1、2、3、4、5、6、7 和二进制 000、001、010、011、100、101、110、111。你看这是简单的计数。

如果我们回想起学生时代，那时我们学习了布尔代数和一点点自动机理论，那么我们就会记得这种计数操作是如何在底层完成的。我们总是翻转最低有效位，并且，如果存在从 1 到 0 的转换，那么我们基本上发生了溢出，并且还必须翻转下一位。这就是二进制加法器的原理。我们想在我们的示例中始终添加 1。因此，将 1 与 0 相加，结果为 1，则不会溢出。但是将 1 加 1，结果为 0，然后我们有一个溢出，必须将 1 加到下一位。这将有效地翻转下一位，依此类推。

这种方法的好处是，我们并不总是需要对所有位进行操作。所以，复杂度不是 O(n)，而是 O(log n)。

其他优势：它非常符合您使用 std::bitset 的要求。

第三个优势，也许不是那么明显：您可以将计算下一个组合的任务与程序的其余部分分离。无需将您的实际任务代码集成到此类功能中。这也是为什么 std::next_permutation 是这样实现的原因。

并且，上述算法适用于所有值，无需排序或其他必要的东西。

那部分是你要求的算法。

下一部分是针对您的请求，即只有某些位可以更改。当然，我们需要指定这些位。而且因为您正在使用 std::bitset 掩码，所以这里没有解决方案。更好的方法是使用索引。意思是，给出允许改变的位的位位置。

然后我们可以使用上面描述的算法，只需要一个额外的间接寻址。所以，我们不使用bits[pos]，而是bits[index[pos]].

可以使用初始化列表轻松地将索引存储在 std::vector 中。我们还可以从字符串或其他任何东西中导出索引向量。我用 std::string 作为例子。

以上所有将导致一些简短/紧凑的代码，只有几行并且易于理解。我还添加了一些使用此功能的驱动程序代码。

请看：

#include <iostream>
#include <vector>
#include <string>
#include <bitset>
#include <algorithm>
#include <cassert>

constexpr size_t BitSetSize = 32U;

void nextCombination(std::bitset<BitSetSize>& bits, const std::vector<size_t>& indices) {

    for (size_t i{}; i < indices.size(); ++i) {

        // Get the current index, and check, if it is valid
        if (const size_t pos = indices[i]; pos < BitSetSize) {

            // Flip bit at lowest positions
            bits[pos].flip();

            // If there is no transition of the just flipped bit, then stop
            // If there is a transition from high to low, then we need to flip the next bit
            if (bits.test(pos))
                break;
        }
    }
}

// Some driver code
int main() {
    // Use any kind of mechanism to indicate which index should be changed or not
    std::string mask{ "x00x0000x000000x00x00x000x000x" };

    // Here, we will store the indices
    std::vector<size_t> index{};
    // Populated the indices vector from the string
    std::for_each(mask.crbegin(), mask.crend(), [&, i = 0U](const char c) mutable {if ('x' == c) index.push_back(i); ++i; });

    // The bitset, for which we want to calculate the combinations
    std::bitset<BitSetSize> bits(0);

    // Play around
    for (size_t combination{}; combination < (1 << (index.size())); ++combination) {

        // This is the do something
        std::cout << bits.to_string() << '\n';

        // calculate the next permutation
        nextCombination(bits, index);
    }
    return 0;
}

此软件已使用 C++17 使用 MSVC 19 社区版编译

如果您有其他问题或需要更多说明，我很乐意回答

只有某些位可以改变的二进制数的所有组合

All combinations of a binary number where only certain bits can change

c++

algorithm

bit-manipulation