生成可能最快的方式所有的n位二进制数 [英] generate all n bit binary numbers in a fastest way possible
问题描述
我如何生成的n位串所有可能的组合？我需要生成的20位字符串所有组合中可能的最快途径。 （我目前的执行情况做有位与右移位操作，但是我正在寻找更快的方法）。
我需要存储的比特串以阵列（或列表），用于相应的十进制数，像 -
0 - ＆GT; 0 0 0
1 - ＆GT; 0 0 1
2 - ＆GT; 0 1 0 ...等。
任何想法？
的（无符号长I = 0; I＆LT;（1＆LT;小于20）; ++ I）{
//用它做什么
}
这是无符号长的是的序列位。
如果你想要的是字符一串0和 1 ，那么你可以转换我来该格式各一次。你也许可以得到一个加速采取的事实，即连续数通常有着漫长的初始子的优势。所以，你可以做这样的事情：
字符位串[21];
为（无符号整数I = 0; I＆≤（1＆其中;小于10）; ++ⅰ）{
write_bitstring10（ⅰ，位串）;
为（无符号整数J = 0; J＆≤（1＆其中;小于10）; ++ j）条{
write_bitstring10（J，比特串+ 10）;
//做些事情位串
}
}
我只从1环上升到2，但我超过50％确实有点像以前那样从比特尽可能多的转换为字符。你可以尝试以下操作：
- 使用更加回路
- 拆分循环不平衡，对可能15-5，而不是10-10
- 在编写一个函数，它的零和一的字符串，并增加了1到它。这是pretty的简单：找到最后一个
0，将其更改为1，变所有后的1s到0。
要恶魔般的优化 write_bitstring 4的倍数是好的，因为在大多数架构，你可以在一个字写时间块复制4个字符：
要启动：
断言（CHAR_BIT == 8）;
uint32_t的位串[21/4]。 //没有字符数组，我们需要确保调整
（（字符*）位串）[20] = 0; // NUL终止
函数定义：
常量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），
// 等等。
};
//可能需要大端版本太多
＃定义查找little_endian_lookup //配置示例
无效write_bitstring20（无符号长值，uint32_t的* DST）{
DST [0] =查找[（值安培; 0xF0000）GT;＆GT; 16];
DST [1] =查找[（值安培; 0x0F000）GT;＆GT; 12];
DST [2] =查找[（值安培; 0x00F00）GT;＆GT; 8];
DST [3] =查找[（值安培; 0x000F0）GT;＆GT; 4〕;
DST [4] =查找[（值安培; 0x0000F）];
}
我没有测试过任何这样：明明你是负责编写一个基准，你可以用它来体验
。How do I generate all possible combinations of n-bit strings? I need to generate all combinations of 20-bit strings in a fastest way possible. (my current implementation is done with bitwise AND and right shift operation, but I am looking for a faster technique).
I need to store the bit-strings in an array (or list) for the corresponding decimal numbers, like --
0 --> 0 0 0
1 --> 0 0 1
2 --> 0 1 0 ... etc.
any idea?
for (unsigned long i = 0; i < (1<<20); ++i) {
// do something with it
}
An unsigned long is a sequence of bits.
If what you want is a string of characters '0' and '1', then you could convert i to that format each time. You might be able to get a speed-up taking advantage of the fact that consecutive numbers normally share a long initial substring. So you could do something like this:
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
}
}
I've only increased from 1 loop to 2 there, but I do a little over 50% as much converting from bits to chars as before. You could experiment with the following:
- use even more loops
- split the loops unevenly, maybe 15-5 instead of 10-10
- write a function that takes a string of zeros and ones, and adds 1 to it. It's pretty easy: find the last
'0', change it to a'1', and change all the'1's after it to'0'.
To fiendishly optimize write_bitstring, multiples of 4 are good because on most architectures you can blit 4 characters at a time in a word write:
To start:
assert(CHAR_BIT == 8);
uint32_t bitstring[21 / 4]; // not char array, we need to ensure alignment
((char*)bitstring)[20] = 0; // nul terminate
Function definition:
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)];
}
I haven't tested any of this: obviously you're responsible for writing a benchmark that you can use to experiment.
这篇关于生成可能最快的方式所有的n位二进制数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
