I am looking for an efficient way to iterate over all n bit non-negative integers which have at most k bits set by flipping one bit at a time.
What is the minimum number of bit flips I need to do to iterate over all n bit non-negative integers with at most k bits set?
I know that if k = n, that is we want to iterate over all n bit non-negative integers then we can use a Gray code. This has the great property that you only ever change one bit to get a new number. However this will typically go via integers with more than k bits if k < n.
To iterate over all values for bit 0: Start with any starting value, then flip bit 0.
To iterate over all values for bits 0, 1: Start with any starting value. Iterate over all values for bit 0. Flip bit 1. Iterate over all values for bit 0.
To iterate over all values for bits 0-2: Start with any starting value. Iterate over all values for bit 0, 1. Flip bit 2. Iterate over all values for bit 0, 1.
To iterate over all values for bits 0-3: Start with any starting value. Iterate over all values for bit 0-2. Flip bit 3. Iterate over all values for bit 0-2. I hope the system is clear now.
Start with i = any value, j = 0. Increase j by 1, determine the lowest bit that is set in j, flip that bit in i. Rinse and repeat.