2進数の組み合わせの検索（一致する1の数字）

Question

2進数の場合 すべての1がすべて指定された番号に対応するすべての一致する2進数を検索するアルゴリズムとは何でしょうか。例えば

： 入力：10010 出力：答えの[10010、10011、10110、10111、11010、11011、11110、11111]

Answer 1

ヒント：あなたは彼ら1を維持したいですあります。したがって、基本的に、あなたのシステムの認識言語は{0}です。

溶液＃1：醜い1

ブリュット力、それを、nは、あなたの数の大きさである2^n個進数を取ります。自分のパターンに合ったものだけを残してください。

溶液＃2：ここでも単純化された1

、あなたは彼らが1を維持したいです。したがって、パターン付きのすべてのバイナリを検索したい場合は、Gとあなたのすべての位置のセットを呼び出してみましょう。あなたの番号はNです。数字はiです。 、あなただけのすべてのバイナリを取らなければならないことを意味

は、文字テーブルのテーブルに2 ^（Ni）の-1なサイズ（のはBという名前を付けましょう）とGに含まれる各位置に1を追加。

例：

入力：10010
G = {1,4}（0系、我々はコンピュータ上にある）

2 ^（ニッケル）を生成-1テーブルを= [000、001、010、100、011、101、110、111]

はBでこれらの数字を入れて（N ヌル放置されている）、あなたの番号を各ヌルを置き換える：
第1ステップ：[1nn1n、1nn1n、1nn1n、1nn1n、1nn1n、1nn1n、1nn1n、1nn1n]
第2工程：[10010、10011、10110、11010、10111、11010、11110、11111]

注：

これらのソリューションは文字列ベースであることを覚えておいてください。おそらく、すべての言語でこれらのソリューションを実装することはできません。アルゴリズムをビット単位で実行する必要がある場合は、バイナリを0から2^N-1にして、バイナリでそれぞれまたはオペレーションを実行してください。（正規表現せずに溶液＃1に等しい）

Answer 2

また

のは、初期値でバイトサイズの変数を考えるいくつかのビットのトリックを使用することができます。（NB：そこ
v = 00010010
は、次の2のパワーを探しますより効果的な方法）今

b = 1 
while (b <= v) 
    b = b << 1 

b = 00100000
メイクマスクbm = b - 1 = 00011111です 反転初期値：
n = not v = 11101101
明確な先行ビット：
mask = n & bm = 00001101

このmask値は、私たちが埋めるために必要なすべてのビットが含まれています。

var 
    v, b, bm, n, mask, sub: Byte; 
begin 
    v := 16 + 2; 
    if v < 2 then 
    Exit; 
    b := 1; 
    while (b <= v) do 
    b := b shl 1; 
    bm := b - 1; 
    n := not v; 
    mask := n and bm; 
    sub := mask; 
    while (sub > 0) do begin 
    Writeln(IntToBin(sub or v, 8)); //binary representation 
    sub := (sub - 1) and mask; 
    end; 
    Writeln(IntToBin(sub or v, 8)); 

出力：

00011111 
00011110 
00011011 
00011010 
00010111 
00010110 
00010011 
00010010