找出从 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 的基数 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 次递归调用。所以应该很快。