/ 猿问

# 生成长度为n且设置了k位的所有二进制字符串

2019-09-02 09:17:40

0111

1011

1101

1110

## 3 回答

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编译器内部函数返回尾随零的数量。如果你使用的是x86的Microsoft编译器，那么内在的就是_BitScanForward。这些都发出bsf 指令，但是其他架构可以使用等价物。如果不是，则考虑使用其中一种方法来计算前面提到的连续零位。这是另一个版本，由于它的除法运算符而往往较慢，但它不需要计算尾随零。

unsigned int t = (v | (v - 1)) + 1;

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

import itertools

def kbits(n, k):

result = []

for bits in itertools.combinations(range(n), k):

s = ['0'] * n

for bit in bits:

s[bit] = '1'

result.append(''.join(s))

return result

print kbits(4, 3)

Output: ['1110', '1101', '1011', '0111']

http://docs.python.org/library/itertools.html#itertools.combinations

combinations(K, setN):

if k > length(setN): return "no combinations possible"

if k == 0: return "empty combination"

# combinations INcluding the first item:

return (first-item-of setN) combined combinations(K-1, all-but-first-of setN)

union combinations(K-1, all-but-first-of setN)

• 3 回答
• 0 关注
• 108 浏览

0/150