3

n ビット文字列の可能なすべての組み合わせを生成するにはどうすればよいですか? 20 ビット文字列のすべての組み合わせを可能な限り高速な方法で生成する必要があります。(私の現在の実装は、ビットごとの AND と右シフト操作で行われますが、より高速な手法を探しています)。

対応する 10 進数のビット文字列を配列 (またはリスト) に格納する必要があります。

0 --> 0 0 0

1 --> 0 0 1

2 --> 0 1 0...など

何か案が？

4

6 に答える 6

7

パイソン

>> n = 3
>> l = [bin(x)[2:].rjust(n, '0') for x in range(2**n)]
>> print l
['000', '001', '010', '011', '100', '101', '110', '111']
于 2012-09-08T08:00:33.727 に答える
3

正確に n 桁のバイナリ表現で 0 から 2^n - 1 までの数値を出力するだけです。

于 2012-09-07T21:53:59.550 に答える
3 
for (unsigned long i = 0; i < (1<<20); ++i) {
    // do something with it
}

Anunsigned long は一連のビットです。

必要な文字列が'0'との場合、毎回その形式に'1'変換できます。i通常、連続する数字は長い最初の部分文字列を共有するという事実を利用して、速度を上げることができる場合があります。したがって、次のようなことができます。

char bitstring[21];
for (unsigned int i = 0; i < (1<<10); ++i) {
    write_bitstring10(i, bitstring);
    for (unsigned int j = 0; j < (1<<10); ++j) {
        write_bitstring10(j, bitstring + 10);
        // do something with bitstring
    }
}

ループは 1 から 2 に増えただけですが、ビットから文字への変換は以前と比べて 50% 強増えています。次のことを試すことができます。

  • さらに多くのループを使用する
  • ループを不均等に分割します。おそらく 10-10 ではなく 15-5 です。
  • 0 と 1 の文字列を取り、それに 1 を加算する関数を作成します。とても簡単です: 最後の を見つけ'0'て a'1'に変更し、その後のすべての'1's を に変更し'0'ます。

極限まで最適化write_bitstringするには、4 の倍数が適しています。ほとんどのアーキテクチャでは、1 つの単語で一度に 4 文字を blit できるからです。

始めること：

assert(CHAR_BIT == 8);
uint32_t bitstring[21 / 4]; // not char array, we need to ensure alignment
((char*)bitstring)[20] = 0; // nul terminate

関数定義:

const uint32_t little_endian_lookup = {
    ('0' << 24) | ('0' << 16) | ('0' << 8) | ('0' << 0),
    ('1' << 24) | ('0' << 16) | ('0' << 8) | ('0' << 0),
    ('1' << 24) | ('1' << 16) | ('0' << 8) | ('0' << 0),
    // etc.
};
// might need big-endian version too

#define lookup little_endian_lookup // example of configuration

void write_bitstring20(unsigned long value, uint32_t *dst) {
    dst[0] = lookup[(value & 0xF0000) >> 16];
    dst[1] = lookup[(value & 0x0F000) >> 12];
    dst[2] = lookup[(value & 0x00F00) >> 8];
    dst[3] = lookup[(value & 0x000F0) >> 4];
    dst[4] = lookup[(value & 0x0000F)];
}

私はこれをテストしていません。明らかに、実験に使用できるベンチマークを作成する責任があります。

于 2012-09-07T21:54:28.723 に答える
0

0から2 ^ n-1までのバイナリ表現ですべての整数を生成することでそれを行うことができます

static int[] res;
    static int n;
    static void Main(string[] args)
    {
        n = Convert.ToInt32(Console.ReadLine());
        res = new int [n];
        Generate(0);

    }

    static void Generate(int start)
    {
        if (start > n)
            return;
        if(start == n)
        {
            for(int i=0; i < start; i++)
            {
                Console.Write(res[i] + " ");
            }
            Console.WriteLine();
        }

        for(int i=0; i< 2; i++)
        {
            res[start] = i;
            Generate(start + 1);
        }
    }
于 2014-12-04T12:25:37.353 に答える
0

このソリューションは Python にあります。(バージョン 2.7 および 3.x で動作するはずです)

>>> from pprint import pprint as pp
>>> def int2bits(n):
    return [(i, '{i:0>{n}b}'.format(i=i, n=n)) for i in range(2**n)]

>>> pp(int2bits(n=4))
[(0, '0000'),
 (1, '0001'),
 (2, '0010'),
 (3, '0011'),
 (4, '0100'),
 (5, '0101'),
 (6, '0110'),
 (7, '0111'),
 (8, '1000'),
 (9, '1001'),
 (10, '1010'),
 (11, '1011'),
 (12, '1100'),
 (13, '1101'),
 (14, '1110'),
 (15, '1111')]
>>>

最大数の幅を見つけてから、必要に応じて最大幅を埋めるために、フォーマットされたすべての文字列の右側にゼロが埋め込まれているバイナリでフォーマットされた int と int をペアにします。(pprint は、このフォーラムのきちんとした印刷物を取得するためのものであり、省略される可能性があります)。

于 2012-09-08T07:53:23.063 に答える
0 
for (i = 0; i < 1048576; i++) {
   printf('%d', i);
}

int バージョン i からバイナリ文字列への変換は、OP の課題として残されています。

于 2012-09-07T21:54:08.183 に答える