Find the amount of integers from 0 to k that AND with x is equal to 0

Question

Given k and x, you have to find the amount of integers i, between 0 and k, such that i AND (bitwise &) x is equal to 0.

1 <= x <= 10^9 1 <= k <= 10^9

|k - x| <= 10^6

I need this to work faster than O(k), which is essentially brute force. I can have many calls to this function.

Answer 1

A AND B = 0 if and only if A * B = 0

So, for each bit of A, you can know for sure that if the given bit is 1, then its pair will necessarily be 0 and, if it is 0, then its pair can be 0 or 1.

So, instead of looping the numbers in the interval and checking whether the condition is true, it's better to iterate the bits of A and create a division whenever it's 0, as each such case multiplies the number of results by 2, whereas it will stay as it is if the bit is 1.

A very simple and adequate solution is to use a while loop where you bitshift the input as many times as the number of bits are needed append the result to the numbers you have.

At the very first bitshift you will create one or two numbers, depending on whether the bit was 1 or 0 (and the negation of this bit is shifted into the one or two numbers).

On subsequent steps, if the bit was 1, then you shift 0 into all the numbers you have so far and, if the bit was 1, then you have to duplicate all your numbers you had so far and shift a 1 into one of the pairs and 0 to the other.

If you need to take into account only numbers that fit into an interval, then you could always work on the shifting of leftmost bits and see what the future magnitude of the numbers you get fit into. For example, if a 32-bit number starts with a 0 or a 1, that already tells you some important information of what range the number will get into.

EDIT

As rossum pointed out, we only need to count these numbers rather than returning them. My answer provided a way of finding these actual numbers, I did not restrict this answer to the search of their count. Hence, as rossum pointed out, we can solve this by looking our interval.

If we are to find all these numbers, then my unedited answer seems to be correct. But, if we are only interested in their count, then some key ideas:

• the total number of such numbers (ignoring the bounds for now) is 2^n where n represents the number of 0 bytes in the original number
• if we processed a few bits, then the remaining number of sub-cases with a bit prefix already set is 2^n' where n' represents the number of 0s that can still be found after the prefix
• whenever we find out that a number with a given bit prefix cannot be inside the bounds that were set, then we can add 2^n' to the number of elements that are outside our bounds
• this way we can prune our search and simplify it
• finally, when we finish our processing, the result will be 2^n - sum(2^n')

Alternatively we can just sum the numbers that are inside the bounds rather than summing the numbers and subtracting them from their potential maximum. The thing which mainly determines what is best to count is the wideness of the bounds we have.

Answer 2

Delete all the 1 bits in x from both k and x. If you delete a 1 bit from k, bump it up to the next higher number.

When you're done, k is the answer:

while(x) {
    lobit = x&-x;
    if (k&lobit) {
        // next value of k with lobit 0
        k+=lobit;
        k&=~(lobit-1);
    }
    // delete lobit from x
    x = (x-lobit)>>1;
    // delete lobit from k
    k = (k & (lobit-1)) | ( ( k & ~(lobit-1) ) >>1);
}
return k

Note that this assumes the interpretation of "between 0 and k" in which there are k numbers between 0 and k. If you think there are k+1 numbers between 0 and k, then add 1 first. If you think there are k-1 numbers between 0 and k, then subtract 1 at the end.