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

问题描述

找到所有包含 k 位集合的长度为 n 的二进制字符串的最佳算法是什么?例如，如果 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 的情况下，我需要一种生成这些的好方法，所以我希望它使用字符串来完成.

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) x86 CPU 固有的 GNU C 编译器返回尾随零的数量.如果您使用 Microsoft 编译器x86，内在是 _BitScanForward.这些都发出 bsf指令，但等效物可能可用于其他体系结构.如果不是，则考虑使用其中一种方法来计算前面提到的连续零位.这是另一个版本由于它的除法运算符，它往往会变慢，但它不会需要计算尾随零.

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

感谢阿根廷的 Dario Sneidermanis，他于 2009 年 11 月 28 日提供了此信息.

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

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