所有可能的长度为n的二进制字符串，其中特定位置的位固定

Question

我需要一种快速方法来查找所有长度为n的二进制字符串，它们的位数固定为m。 A C++11兼容功能，其例如采用std:map，其中键为固定位的位置，值为固定位的值。输出std::bitset<n> s或std::vector<n>的矢量将会很好。 E.g功能：

std::vector< std::bitset<n> > compatible(int n, const std::map<int,bool>& fix) 

例如，如果n=3我们固定第二位为1，那么答案应该是

{{0,1,0},{0,1,1},{1,1,0},{1,1,1}} 

当顺序并不重要。

如果另一个数据结构更快，那么我更喜欢速度。如果n < 50也可以在64位体系结构上实现显着的加速，那么这也会很有趣。

Answer 1

有一个相对简单的整数运算方法，它通过以不影响固定位的特殊增量循环遍历所有的可能性。

即增量是

x = (x | isfixed) + 1 & ~isfixed | fixedvalue; 

第一或使固定位置1，这意味着从1的进位将通过它们。然后固定位被恢复到它们的正确值。

或者，如果你有机会到_pdep_u64或同等学历，你可以只使用一个普通的老循环在从0所有整数2 ^纳米，然后蔓延位的所有非固定位置与_pdep_u64(i, ~isfixed)，然后填写固定职位。