What is the best way to enumerate all the numbers between 1 to n having kth bit set?

Question

What is the best way to enumerate all the numbers between 1 to n having kth bit set?

For example:
when n = 12 and k = 1, answer will be 1, 3, 5, 7, 9, 11.
If k = 2, answer will be 2, 3, 6, 7, 10, 11.

One trivial approach is to loop over n and check if kth bit is set (by checking num & (1 << (k-1)) is 1 or 0) but is there any better way to do this?

Answer 1

If you increment the number and there should be a carry from the part below k to the part above k, that carry will propagate across and leave the kth bit 0, otherwise it stays 1.

So all you need to do is switch the kth bit back on:

x = (x + 1) | (1 << k);

Just loop that until you've reached your upper bound, sort of like this (just an example)

for (int x = 1 << k; x < n; x = (x + 1) | (1 << k))
    print(x); // or whatever

Answer 2

Assuming that we have n bits, and bit k is fixed to 1, so those number we looking for will look like xxxx1xxxx, so we only need to generate all numbers with (n - 1) bits.

For example, if we have 3 bits, and we want bit 2 is set, so we only need to generate 2^(n - 1) = 4 numbers, and the final numbers look like : x1x

so these numbers are 0(00) , 1(01) , 2(10), 3(11) -> add in bit 2, the final number we look for is 2(010), 3(011), 6(110), 7(111)

Pseudo code:

   int n = ...//User input
   int bit = numberOfBitUsed(n)
   for(int i = 0; i < (1<<bit); i++){
       int number = generateNumber(i, k);
       if(number > n){
          break;
       }

   }

Note: with some bit manipulations, we can implement generateNumber(int number, int k) with O(1) time complexity

 int generateNumber(int val, int k){
    int half = Integer.MAX_VALUE & ~((1<<k) - 1);//Mask for bit from 31 to k 
    int a = half & val;
    a <<=1;
    int b = ((1<<k) - 1) & val;
    int num = a | b | (1<<k);
    return num;
 }