This problem is from the 2011 Codesprint (http://csfall11.interviewstreet.com/):
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
Sample Input: 3 -2 0 -3 4 -1 4 Sample Output: 63 99 37
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
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!
To get 1's complement of a binary number, simply invert the given number. To get 2's complement of a binary number, simply invert the given number and add 1 to the least significant bit (LSB) of given result.
An N-bit ones' complement numeral system can only represent integers in the range −(2N−1−1) to 2N−1−1 while two's complement can express −2N−1 to 2N−1−1. It is one of three common representations for negative integers in microprocessors, along with two's complement and sign-magnitude.
In general, the range of an N-bit two's complement number spans [−2N−1, 2N−1 − 1]. It should make sense that there is one more negative number than positive number because there is no −0.
However a two's complement 8-bit number can only represent positive integers from 0 to 127 (01111111), because the rest of the bit combinations with the most significant bit as '1' represent the negative integers −1 to −128.
Well, it's not that complicated...
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) ;
}
It only works for non-negative a, and it counts the number of 1 bits in all integers from 0 to a
inclusive.
The function has three cases:
a == 0
-> returns 0. Obviously.
a
even -> returns the number of 1 bits in a
plus solve(a-1)
. Also pretty obvious.
The final case is the interesting one. So, how do we count the number of 1 bits from 0 to an odd number a
?
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)
and
001 (aka 1)
011 (aka 3)
101 (aka 5)
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
...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.)
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.
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).
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With