以最快的方式生成所有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); 
     } 
    }