長さnの可能なすべてのバイナリ文字列と特定の位置のビットを固定

Question

長さがnで、ビットがmの固定であるすべてのバイナリ文字列を見つけるには、高速な方法が必要です。例えば、std:mapをキーで固定ビットの位置とし、固定ビットの値をとる互換性のある機能であるC++11がある。 std::bitset<n>またはstd::vector<n>のベクトルを出力すると良いでしょう。例えば機能：たとえば

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

n=3あれば、我々は答えは順序が重要ではありません

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

である必要があり、その後1への第2ビットを修正。

他のデータ構造がはるかに速い場合、私はスピードを優先します。また、もしも64ビットアーキテクチャ上でかなりのスピードアップが達成できれば、n < 50それはまた興味深いでしょう。

Answer 1

固定ビットに影響を与えない特別な増分で2 ⁿの可能性をループすることで、整数計算でかなり簡単な方法があります。

すなわち増分

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

第1のOR +1からキャリーがそれらを通過することを意味する、固定位置1になります。その後、固定ビットはそれらの適切な値に復元される。

あなたが_pdep_u64または同等へのアクセス権を持っている場合は別の方法として、あなただけの0から2までのすべての整数の上に、昔ながらのループを使用することができます^nmの、そしてその後、_pdep_u64(i, ~isfixed)ですべての非固定位置にビットを広めます固定された位置に記入してください。