这个问题是从2011年的codesprint（http://csfall11.interviewstreet.com/）：

This problem is from the 2011 Codesprint (http://csfall11.interviewstreet.com/):

一台计算机科学的基础知识是知道如何号码重新psented 2的补$ P $。试想一下，你记下A和B（含）之间的所有数字2的补重$ P $使用32位psentation。在所有的有多少1的会写下来吗？ 输入： 第一行包含测试用例T（＆所述; 1000）的数量。每下一个Ť行包括两个整数A和B的 输出： 输出T线路，一个对应于每个测试用例。 约束： -2 ^ 31＆LT; = A＆LT; = B＆LT; = 2 ^ 31 - 1

One of the basics of Computer Science is knowing how numbers are represented in 2's complement. Imagine that you write down all numbers between A and B inclusive in 2's complement representation using 32 bits. How many 1's will you write down in all ? Input: The first line contains the number of test cases T (<1000). Each of the next T lines contains two integers A and B. Output: Output T lines, one corresponding to each test case. Constraints: -2^31 <= A <= B <= 2^31 - 1

采样输入： 3 -2 0 -3 4 -1 4 示例输出： 63 99 37

Sample Input: 3 -2 0 -3 4 -1 4 Sample Output: 63 99 37

说明： 对于第一种情况，-2含有31 1的后跟一个0，-1包含32个1和0中包含0 1的。因此，总是63。 对于第二种情况，答案是31 + 31 + 32 + 0 + 1 + 1 + 2 + 1 = 99

Explanation: For the first case, -2 contains 31 1's followed by a 0, -1 contains 32 1's and 0 contains 0 1's. Thus the total is 63. For the second case, the answer is 31 + 31 + 32 + 0 + 1 + 1 + 2 + 1 = 99

我知道你可以使用一个事实，即在-X 1的个数等于0的在（-X）的补数= X-1到加速搜索。解决的办法宣称，有一个为O（log X）递推关系产生答案，但我不理解这一点。该解决方案code可以在这里查看： https://gist.github.com/1285119

I realize that you can use the fact that the number of 1s in -X is equal to the number of 0s in the complement of (-X) = X-1 to speed up the search. The solution claims that there is a O(log X) recurrence relation for generating the answer but I do not understand it. The solution code can be viewed here: https://gist.github.com/1285119

我会AP preciate，如果有人可以解释这种关系是如何得出！

I would appreciate it if someone could explain how this relation is derived!

推荐答案

嗯，这不是的是的复杂...

Well, it's not that complicated...

单参数解决（INT一）功能是关键。它是短暂的，所以我会削减和放大器，在这里贴：

The single-argument solve(int a) function is the key. It is short, so I will cut&paste it here:

long long solve(int a)
{
 if(a == 0) return 0 ;
 if(a % 2 == 0) return solve(a - 1) + __builtin_popcount(a) ;
 return ((long long)a + 1) / 2 + 2 * solve(a / 2) ;
}

这仅适用于非负的一个，它计算的1位为0的所有整数数 A 的包容性。

该功能有三种情况：

A == 0 - >返回0。显然

a == 0 -> returns 0. Obviously.

A 什 - >返回1位 A 加上解决数（ A-1）。另外pretty的明显。

a even -> returns the number of 1 bits in a plus solve(a-1). Also pretty obvious.

最后一种情况是有趣的。那么，我们该如何算1位的数量从0到奇数 A ？

The final case is the interesting one. So, how do we count the number of 1 bits from 0 to an odd number a?

考虑所有介于0和整数的，然后将它们分成两组：本唇上，和赔率。例如，如果 A 5，你有两个组（二进制）：

Consider all of the integers between 0 and a, and split them into two groups: The evens, and the odds. For example, if a is 5, you have two groups (in binary):

000  (aka. 0)
010  (aka. 2)
100  (aka. 4)

和

001  (aka 1)
011  (aka 3)
101  (aka 5)

注意，这两个群体必须有相同的大小（因为 A 是奇数，范围是包括在内）。要计算有多少1位有每个组中，先算所有，但最后一位，再算上最后一位。

Observe that these two groups must have the same size (because a is odd and the range is inclusive). To count how many 1 bits there are in each group, first count all but the last bits, then count the last bits.

除了最后位看起来是这样的：

All but the last bits looks like this:

00
01
10

......，它看起来像这样的两个的群体。 1位的数字在这里只是解决（A / 2）。 （在这个例子中，它是1个位从0到2。此外数量，回想在C / C ++弹，整数除法的向下的。）

...and it looks like this for both groups. The number of 1 bits here is just solve(a/2). (In this example, it is the number of 1 bits from 0 to 2. Also, recall that integer division in C/C++ rounds down.)

的最后一位是零为第一组中的每一个数字和一个用于第二组中的每一个号码，因此那些最后位贡献（A + 1）/ 2 1位的总

The last bit is zero for every number in the first group and one for every number in the second group, so those last bits contribute (a+1)/2 one bits to the total.

所以递归的第三种情况是（A + 1）/ 2 + 2 *解决（A / 2），适当的强制转换为很长很长处理的情况下，其中 A 是 INT_MAX （因而 A + 1 溢出）。

So the third case of the recursion is (a+1)/2 + 2*solve(a/2), with appropriate casts to long long to handle the case where a is INT_MAX (and thus a+1 overflows).

这是一个O（日志N）解决方案。概括为解决（A，B），你只需计算解决（二） - 解（一），加上担心负数适当的逻辑。这就是这两个参数的解决（INT A，INT B）在做什么。

This is an O(log N) solution. To generalize it to solve(a,b), you just compute solve(b) - solve(a), plus the appropriate logic for worrying about negative numbers. That is what the two-argument solve(int a, int b) is doing.