用于生成k位设置为1的n个二进制数字的有效代码是什么？ [英] What is an efficient code for generating n binary digit numbers with k bits set as one?

问题描述

是否有任何有效的代码来生成二进制表示形式的n位数字，并且将r位设置为1？

Is there any efficient code to generate numbers with n digits in their binary representation with exactly r bits set as one?

这也是生成掩码的一种好策略为查找集合的NcR个组合？

Also is this a good strategy to generate masks for finding NcR combinations of a set?

我曾考虑过生成所有2 ^ n个数字并计算它们的位数，但计数位数似乎是O（nlogn）。 / p>

I've thought about generating all 2^n numbers and counting their bits but counting bits seems to be O(nlogn).

推荐答案

如果给定一个设置了K位的数字，我们怎么能找到下一个最大的 >设置了K位的数字？如果我们重复执行此操作，则可以生成所有这些。

Well, if we are given a number with K bits set, how can we find the next largest number with K bits set? If we do this repeatedly we can generate all of them.

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

Generating the next one breaks down to a couple simple rules:

1. 要更改的最高位必须从0更改为1。否则，新数字将小于给定的数字。


2. 更改的最高位必须是最低的一位。否则，当前数字和新数字之间将存在其他有效数字。当我们将一个位从0更改为1时，我们必须将另一个位从1更改为0，并且该位必须更小，因此我们要从0更改为1的高位是最低的0位（带有1位）


3. 其余的低位必须设置为最小的有效配置。否则，在当前数字和新数字之间将再次存在其他有效数字。低位的最小有效配置是所有1位都位于最低位置的配置。

1. The highest bit that changes must change from 0 to 1. Otherwise the new number would be smaller than the given one.
2. The highest bit that changes must be the lowest one possible. Otherwise there would be other valid numbers between the current one and the new one. When we change a bit from 0 to 1, we have to change another bit from 1 to 0, and this bit has to be smaller, so the high bit we want to change from 0 to 1 is the lowest 0 bit with a 1 bit in a lower position.
3. The remaining lower bits must be set to their smallest valid configuration. Otherwise there would again be other valid numbers between the current one and the new one. The smallest valid configuration for the lower bits is the one with all the 1 bits in the lowest positions.

事实证明有可轻松实现所有这些规则的二进制数学小技巧。在Python中是这样的：

It turns out that there are little binary math tricks that implement all these rules easily. Here it is in 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条规则来增加该数组。

If you want to enumerate NcR combinations using bitmasks, then this is a good way to do it. If you would prefer to have, say, an array of indexes of the chosen items, then it would be better to use a different procedure. You can make 3 rules like the above for incrementing that array too.

这篇关于用于生成k位设置为1的n个二进制数字的有效代码是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！