Find the number of pairs of natural numbers from l to r which Bitwise AND is equal to 0

Question

Given l and r, find the number of pairs of natural numbers from l to r which Bitwise AND is equal to 0.

Limits :

1 <= l <= r <= 10^9

r - l <= 10^6

I could only write a brute force. Does anyone have an idea how to solve this task? The range size is upto 10^6, so we could use that somehow.

Answer 1

First write the following function:

def and_i_lt_k  (i, k):
    ## Will return the number of numbers in the range 0..k
    ## whose and with i is 0
    ...

You can write that with your point about the bits - you just find the biggest nonzero bits that can work staying in range, remove the bits that MUST be 0, and you have the base 2 representation of one less than the number of ands that meet the condition. (The counting trick missed 0.)

And now we use the following fact. Suppose that x & y == 0. Then:

1. (2*x) & (2*y) == 0
2. (2*x + 1) & (2*y) == 0
3. (2*x) & (2*y + 1) == 0

But (2*x + 1) & (2*y + 1) == 1.

So we can pair up most of the range from l to r, drop the bottom bit from l and r to get a smaller range, count the ands of the range, and then multiply by 3. We also have to be careful with the boundaries. So we get something like this:

def pairs_and_0 (l, r):
    # Base case
    if l == r:
      if l == 0:
          return 1
      else:
          return 0

    # Recursion.
    edge_pairs = 0
    # Edge case for the l-1 trick we will use.
    if 0 == l:
        edge_pairs += r
        l += 1

    # Is the top the first in an incomplete pair?
    if 0 == r%2:
        edge_pairs += and_i_lt_k(r, r) - and_i_lt_k(r, l-1)
        r -= 1

    # Is the bottom the second in an incomplete pair?
    if 1 == l%2:
        edge_pairs += and_i_lt_k(l, r) - and_i_lt_k(l, l-1)
        l += 1

    return edge_pairs + 3 * pairs_and_0(l//2, r//2)

This will be only 20 recursive calls to a trivial range. So it should be quite fast.