CODEWITHSUNDEEP
algorithmdata-structures
saurav
saurav

Reputation: 41

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

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?

Upvotes: 4

Views: 197

Answers (2)

user555045
user555045

Reputation: 64904

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

Upvotes: 7

Pham Trung
Pham Trung

Reputation: 11284

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;
 }

Upvotes: 2

Related Questions