范围内整数的二进制补码二进制表示中 1 的数量 [英] Number of 1s in the two's complement binary representations of integers in a range
问题描述
这个问题来自 2011 Codesprint (http://csfall11.interviewstreet.com/):
This problem is from the 2011 Codesprint (http://csfall11.interviewstreet.com/):
计算机科学的基础之一是了解数字在 2 的补码中的表示方式.想象一下,您使用 32 位以 2 的补码表示形式写下 A 和 B 之间的所有数字.你一共要写多少个1?输入:第一行包含测试用例的数量 T (<1000).接下来的 T 行中的每一行都包含两个整数 A 和 B.输出:输出 T 行,一个对应每个测试用例.约束:-2^31 <= A <= B <= 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样本输出:639937
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 的数量等于 (-X) = X-1 的补码中 0 的数量这一事实来加快搜索速度.该解决方案声称存在用于生成答案的 O(log X) 递归关系,但我不明白.解决方案代码可以看这里: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
如果有人能解释这种关系是如何得出的,我将不胜感激!
I would appreciate it if someone could explain how this relation is derived!
推荐答案
嗯,没那么复杂...
单参数solve(int a)
函数是关键.它很短,所以我将在此处剪切和粘贴:
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) ;
}
它只对非负a有效,它计算从0到a
(含)所有整数中1的位数.
It only works for non-negative a, and it counts the number of 1 bits in all integers from 0 to a
inclusive.
函数分三种情况:
a == 0
-> 返回 0.显然.
a == 0
-> returns 0. Obviously.
a
even -> 返回 a
中 1 的位数加上 solve(a-1)
.也很明显.
a
even -> returns the number of 1 bits in a
plus solve(a-1)
. Also pretty obvious.
最后一个案例很有趣.那么,我们如何计算从 0 到奇数 a
的 1 位数呢?
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
之间的所有整数,并将它们分成两组:偶数和赔率.例如,如果 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
...both 组看起来像这样.这里 1 的位数就是 solve(a/2)
.(在这个例子中,它是从 0 到 2 的 1 的位数.另外,请回忆一下 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
一位.
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*solve(a/2)
,适当的转换为long long
来处理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(log N) 的解决方案.要将其推广到 solve(a,b)
,您只需计算 solve(b) -solve(a)
,加上担心负数的适当逻辑.这就是两个参数 solve(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.
这篇关于范围内整数的二进制补码二进制表示中 1 的数量的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!