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

首先编写如下函数：

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 的位，然后你就得到了比满足的 and 的数量少 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底部位以获得更小的范围，计算该范围的与，然后乘以 3。我们还必须小心边界。所以我们得到这样的东西：lr

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 次递归调用。所以它应该是相当快的。