生成长度为n的所有二进制字符串k位设置 [英] Generate all binary strings of length n with k bits set

问题描述

什么是最好的算法来查找长度为n包含k位设置的所有二进制字符串？例如，如果n = 4且k = 3，有...

What's the best algorithm to find all binary strings of length n that contain k bits set? For example, if n=4 and k=3, there are...

0111
1011
1101
1110

我需要一个很好的方法来生成这些给定的任何n和任意k，所以我倒是preFER它与字符串进行。

I need a good way to generate these given any n and any k so I'd prefer it to be done with strings.

推荐答案

此方法会产生与完全N'1'比特的所有整数。

This method will generate all integers with exactly N '1' bits.

从 https://graphics.stanford.edu/~seander/bithacks.html #NextBitPermutation

假设我们有N位的整数设置为1的模式，我们希望   N + 1位在词典编纂意义上的下一个排列。对于   例如，如果N是3和位图案为 00010011 ，系统的下一个图案   将 00010101 ， 00010110 ， 00011001 ， 00011010 ， 00011100 ， 00100011 ，   等等。下面是一个快速的方法来计算下一个   排列。

Compute the lexicographically next bit permutation

Suppose we have a pattern of N bits set to 1 in an integer and we want the next permutation of N 1 bits in a lexicographical sense. For example, if N is 3 and the bit pattern is 00010011, the next patterns would be 00010101, 00010110, 00011001, 00011010, 00011100, 00100011, and so forth. The following is a fast way to compute the next permutation.

unsigned int v; // current permutation of bits
unsigned int w; // next permutation of bits

unsigned int t = v | (v - 1); // t gets v's least significant 0 bits set to 1
// Next set to 1 the most significant bit to change,
// set to 0 the least significant ones, and add the necessary 1 bits.
w = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(v) + 1));

     

在 __ builtin_ctz（V） GNU C编译器内在的x86处理器返回尾随零的个数。如果您使用的是Microsoft编译器   86，内在是 _BitScanForward 。这些既发出 BSF   指令，但当量可提供其他架构。   如果没有，那么可以考虑使用的方法之一进行计数的   连续0位前面提到的。这里是另一个版本   往往是因为它的除法运算的速度较慢，但​​它没有   需要计算尾随零。

The __builtin_ctz(v) GNU C compiler intrinsic for x86 CPUs returns the number of trailing zeros. If you are using Microsoft compilers for x86, the intrinsic is _BitScanForward. These both emit a bsf instruction, but equivalents may be available for other architectures. If not, then consider using one of the methods for counting the consecutive zero bits mentioned earlier. Here is another version that tends to be slower because of its division operator, but it does not require counting the trailing zeros.

unsigned int t = (v | (v - 1)) + 1;
w = t | ((((t & -t) / (v & -v)) >> 1) - 1);

     

由于达里奥Sneidermanis阿根廷，谁提供了这个11月28日，2009年

Thanks to Dario Sneidermanis of Argentina, who provided this on November 28, 2009.

这篇关于生成长度为n的所有二进制字符串k位设置的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！