此问题来自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
如果有人能解释这种关系是如何产生的,我将不胜感激!