以最快的方式生成所有n位二進制數

Question

如何生成n位串的所有可能組合？我需要以最快的方式生成20位字符串的所有組合。 （我目前的實現是按位AND和右移操作完成的，但我正在尋找更快的技術）。

我需要存儲在陣列中的比特串（或單）對應的十進制數，就像 -

0 --> 0 0 0

1 --> 0 0 1

2 --> 0 1 0 ...等

有什麼想法？

Answer 1

for (unsigned long i = 0; i < (1<<20); ++i) { 
    // do something with it 
} 

一種unsigned 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％，從位像以前那樣多的轉換爲字符。你可以通過下面的試驗：

• 使用更環路
• 拆分循環不均勻，也許15-5，而不是10-10
• 寫一個函數，零和的字符串，給它增加1。這很容易：找到最後的'0'，將其更改爲'1'，並將其後的所有'1'更改爲'0'。

爲了惡魔般的優化write_bitstring，爲4的倍數是一件好事，因爲在大多數系統架構，你可以在一個字寫入時間的blit 4個字符：

要啓動：

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)]; 
} 

我還沒有測試過這些：顯然你負責編寫一個您可以用來進行實驗的基準。

Answer 2

只需輸出數字從0到2^n - 1的二進制表示正好有n個數字。

Answer 3

for (i = 0; i < 1048576; i++) { 
    printf('%d', i); 
} 

將int版本i轉換爲二進制字符串作爲練習保留給OP。

Answer 4

該解決方案使用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整型二進制格式與每一個格式化字符串是右補齊零的如果需要的話，以填補最大寬度。 （pprint的東西只是爲了得到一個整潔的打印輸出這個論壇，可以省略）。

Answer 5

的Python

>> 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'] 

Answer 6

你可以做到這一點通過生成的二進制形式的所有整數從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); 
     } 
    }