What's the best way to list all numbers from 1 to n that have the kth bit?
What's the best way to list all the numbers from 1 to n
with the bit set kth
?
For example:
when n = 12
and k = 1
, the answer will be 1, 3, 5, 7, 9, 11
.
If k = 2
, the answer will be 2, 3, 6, 7, 10, 11
.
One trivial approach is to iterate over n
and check if a bit is set kth
(by checking num & (1 << (k-1))
is 1
or 0
), but is there a better way to do this?
source to share
If you increase the number, and there must be a carry from the part below k to the part above k, then the carry will propagate across and leave the kth bit at 0, otherwise it will remain at 1.
So all you have to do is toggle the kth bit again:
x = (x + 1) | (1 << k);
Just run the loop until you reach the top border, sort of like (example)
for (int x = 1 << k; x < n; x = (x + 1) | (1 << k))
print(x); // or whatever
source to share
Suppose we have n bits and k bit is fixed to 1, so the number we are looking for will look like xxxx1xxxx
, so we just need to generate all numbers with (n - 1) bits.
For example, if we have 3 bits and we want bit 2 to be set, we only need to create 2 ^ (n - 1) = 4 numbers, and the final numbers look like this: x1x
so these numbers are 0 (00), 1 (01), 2 (10), 3 (11) -> add to bit 2, the final number we are looking for is 2 (010), 3 (011), 6 (110 ), 7 (111)
Pseudocode:
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 manipulation, 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;
}
source to share