一个范围内整数的二进制补码表示中的1的数量

Question

此问题来自2011 Codesprint(http://csfall11.interviewstreet.com/):

计算机科学的基础之一是知道数字如何以2的补码表示.想象一下,使用32位写下A和B之间的所有数字,包括2的补码表示.你会写下多少1？输入:第一行包含测试用例数T(<1000).每个下一个T行包含两个整数A和B.输出:输出T行,一行对应于每个测试用例.约束:-2 ^ 31 <= A <= B <= 2 ^ 31 - 1

样品输入:3 -2 0 -3 4 -1 4样品输出:63 99 37

说明:对于第一种情况,-2包含31 1后跟0,-1包含32 1和0包含0 1.因此,总是63.对于第二种情况,答案是31 + 31 + 32 + 0 + 1 + 1 + 2 + 1 = 99

我意识到你可以使用-X中的1的数量等于(-X)= X-1的补码中的0的数量以加速搜索的事实.该解决方案声称有一个O(log X)递归关系用于生成答案但我不明白.解决方案代码可以在这里查看:https://gist.github.com/1285119

如果有人能解释这种关系是如何产生的,我将不胜感激!

Answer 1

好吧,这不是那个复杂...

单参数solve(int a)函数是关键.它很短,所以我将它剪切并粘贴在这里:

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) ;
}

它仅适用于非负a,它计算从0到a包含的所有整数中的1位数.

该功能有三种情况:

a == 0 - >返回0.显然.

aeven - >返回a加1的1位数solve(a-1).也很明显.

最后一个案例是有趣的.那么,我们如何计算从0到奇数的1位数a？

考虑0和之间的所有整数a,并将它们分成两组:平均值和赔率.例如,如果a是5,则您有两个组(二进制):

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

和

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

请注意,这两个组必须具有相同的大小(因为它a是奇数,范围是包含的).要计算每组中有多少1位,首先计算除最后位之外的所有位,然后计算最后位.

除最后一位之外的所有位都是这样的:

00
01
10

......对于这两个群体来说,它看起来都像这样.这里的1位数就是solve(a/2).(在这个例子中,它是从0到2的1位数.另外,回想一下C/C++中的整数除法向下舍入.)

对于第一组中的每个数字,最后一位为零,对于第二组中的每个数字,最后一位为0,因此最后(a+1)/2一位对总数贡献一位.

因此,递归的第三种情况是(a+1)/2 + 2*solve(a/2),用适当的强制转换成long long处理其中的情况下a是INT_MAX(并因此a+1溢出).

这是一个O(log N)解决方案.要概括它solve(a,b),你只需计算solve(b) - solve(a),加上适当的逻辑来担心负数.这就是两个论点solve(int a, int b)正在做的事情.