In a comment on the prior exercise, Richard A. O’Keefe said:

This is just the “next k-subset of 1..n” problem. It is possible to go fairly directly from one popc-k integer to the next. Let the least significant 1 bit be at offset p. If bit(p+1) is 0, set it to 1 and clear bit(p). If bit(p+1) is 1, clear bit(p), set bit(0), advance bits (p+1..msb) to the next integer with k-1 bits.

The algorithm at the top of the page is spectacularly inefficient. Consider the case of 32-bit integers, bit(30) is on, and all the others are off. (k=1) The (next n) algorithm loops about 2**30 times.

Dr. O’Keefe is correct. My solution isn’t very good. In fact, it’s abominable.

Your task is to write a program to solve the next-identical-popcount problem in the manner Professor O’Keefe suggests. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisements

Pages: 1 2