algorithm - 查找从 l 到 r 中按位与等于 0 的自然数对的数量

Question

给定 l 和 r，找到从 l 到 r 中按位与等于 0 的自然数对的数量。

限制:

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

r - l <= 10^6

我只能写一个蛮力。有谁知道如何解决这个任务？范围大小最大为 10^6，因此我们可以以某种方式使用它。

Answer 1

首先编写以下函数:

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

你可以用关于位的观点来写——你只需找到可以在范围内工作的最大非零位，删除必须为 0 的位，然后你就得到了比 1 的数量少 1 的基数 2 表示。并且满足条件。 (计数技巧错过了 0。)

现在我们使用以下事实。假设 x & y == 0。然后:

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

但是(2*x + 1) & (2*y + 1) == 1。

因此，我们可以将 l 到 r 的大部分范围配对，从 l 和 r< 中删除底部位 要获得更小的范围，请计算该范围的与，然后乘以 3。我们还必须小心边界。所以我们得到这样的东西:

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)

这只是对一个微不足道的范围进行 20 次递归调用。所以它应该相当快。