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

Question

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

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

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

HAKMEM 175 describes method for finding the next higher integer with same number of bits set, check related answer. — niemmi
If n is (less than) the size of a machine word, you can count the 1's in constant time - but you shouldn't use this approach anyway, 2^n is a lot bigger than the actual number of combinations. — harold
Possible duplicate of Generate all binary strings of length n with k bits set — m69 ''snarky and unwelcoming''

Matt Timmermans Matt Timmermans · Accepted Answer · 2017-09-03T14:26:10

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:

The highest bit that changes must change from 0 to 1. Otherwise the new number would be smaller than the given one.
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.
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.

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)

You can try it out here: https://ideone.com/ieWaUW

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.

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

1 Answers