Encontre o número de pares de números naturais de l a r que bit a bit AND é igual a 0

Primeiro escreva a seguinte função:

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

Você pode escrever isso com seu ponto sobre os bits - você apenas encontra os maiores bits diferentes de zero que podem funcionar permanecendo no intervalo, remove os bits que DEVEM ser 0 e você tem a representação de base 2 de um a menos que o número de ands que atendem a condição. (O truque da contagem falhou 0.)

E agora usamos o seguinte fato. Suponha que x & y == 0. Então:

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

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

Portanto, podemos emparelhar a maior parte do intervalo de la r, diminuir a parte inferior de le rpara obter um intervalo menor, contar os ands do intervalo e, em seguida, multiplicar por 3. Também precisamos ter cuidado com os limites. Assim, obtemos algo assim:

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)

Serão apenas 20 chamadas recursivas para um intervalo trivial. Então deve ser bem rápido.