什么是生成 k 位设置为 1 的 n 个二进制数字的有效代码？

Question

是否有任何有效的代码可以生成 n 位二进制表示形式且正好 r 位设置为 1 的数字？

此外，这是生成用于查找集合的 NcR 组合的掩码的好策略吗？

我考虑过生成所有 2^n 个数字并计算它们的位数，但计算位数似乎是 O(nlogn)。

Answer 1

嗯，如果给定一个设置了 K 位的数字，我们如何找到设置了 K 位的下一个最大 数字？如果我们重复这样做，我们可以生成所有这些。

生成下一个分解为几个简单的规则：

改变的最高位必须从0变为1。否则新的数字会小于给定的数字。
改变的最高位必须是最低位。否则在当前数字和新数字之间会有其他有效数字。当我们把一个位从0变成1的时候，我们还要再把一个位从1变成0，而且这个位要小一点，所以我们要从0变成1的高位就是最低的0位加上一个1位处于较低的位置。
其余的低位必须设置为其最小的有效配置。否则，在当前数字和新数字之间还会有其他有效数字。低位的最小有效配置是所有 1 位都在最低位置的配置。

事实证明，几乎没有二进制数学技巧可以轻松实现所有这些规则。这是在 python:

N = 6 # length of numbers to generate
K = 4 # number of bits to be set

cur = (1<<K)-1  #smallest number witk K bits set

while cur < (1<<N):

    print format(cur,'b')

    #when you subtract 1, you turn off the lowest 1 bit
    #and set lower bits to 1, so we can get the samallest 1 bit like this:
    lowbit = cur&~(cur-1)

    #when you add lowbit, you turn it off, along with all the adjacent 1s
    #This is one more than the number we have to move into lower positions
    ones = cur&~(cur+lowbit)

    #cur+lowbit also turns on the first bit after those ones, which
    #is the one we want to turn on, so the only thing left after that
    #is turning on the ones at the lowest positions
    cur = cur+lowbit+(ones/lowbit/2)

您可以在这里尝试：https://ideone.com/ieWaUW

如果您想使用位掩码枚举 NcR 组合，那么这是一个很好的方法。如果您希望拥有所选项目的索引数组，那么最好使用不同的过程。您也可以像上面那样制定 3 条规则来递增该数组。

什么是生成 k 位设置为 1 的 n 个二进制数字的有效代码？

What is an efficient code for generating n binary digit numbers with k bits set as one?

algorithm

combinations

bitmask