Este problema é da Codesprint 2011 http: //csfall11.interviewstreet.com):

Um dos fundamentos da Ciência da Computação é saber como os números são representados no complemento de 2. Imagine que você anote todos os números entre A e B, inclusive na representação do complemento de 2, usando 32 bits. Quantos 1 você anotará no total? Entrada: A primeira linha contém o número de casos de teste T (<1000). Cada uma das próximas linhas T contém dois números inteiros A e B. Saída: Linhas T de saída, uma correspondente a cada caso de teste. Restrições: -2 ^ 31 <= A <= B <= 2 ^ 31 - 1

Entrada de amostra: 3 -2 0 -3 4 -1 4 Saída de amostra: 63 99 37

Explicação: Para o primeiro caso, -2 contém 31 1's seguidos por um 0, -1 contém 32 1's e 0 contém 0 1's. Assim, o total é 63. Para o segundo caso, a resposta é 31 + 31 + 32 + 0 + 1 + 1 + 2 + 1 = 99

Sei que você pode usar o fato de que o número de 1s em -X é igual ao número de 0s no complemento de (-X) = X-1 para acelerar a pesquisa. A solução afirma que existe uma relação de recorrência O (log X) para gerar a resposta, mas eu não a entendo. O código da solução pode ser visualizado aqui:https: //gist.github.com/128511

Eu apreciaria se alguém pudesse explicar como essa relação é derivad