InterviewStreet,

## Problem:

2's complement (10 Points)
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

The big part of this problem is to deal with the big number, the programmer needs to convert the integer to long very first, then do the other operations.

## Source Code:

/**
* Problem: 2's complement, from interviewStreet.
*
* The solution is from the link, which reached a log(n) time complexity on this
* one.
*/

/**
* @author antonio081014
* @since Jan 5, 2012, 1:41:35 PM
*/
public class Solution {

public static void main(String[] args) throws Exception {
// new DataInputStream(new FileInputStream(args))));
// BufferedWriter bw = new BufferedWriter(new FileWriter(args));
for (int t = 1; t <= T; t++) {
int a = Integer.parseInt(str);
int b = Integer.parseInt(str);
System.out.println(solve(a, b));
// bw.write(Long.toString(solve(a, b)) + "\n");
}
br.close();
// bw.close();
}

/**
* http://stackoverflow.com/questions/7942732/number-of-1s-in-the-twos-
* complement-binary-representations-of-integers-in-a-ran
*
* The explanation greatly explans everything.
*
* */
public static long solve(int a, int b) {
if (a >= 0) {
long ret = counter(b);
if (a > 0)
ret -= counter(a - 1);
return ret;
}
long ret = ((long32 * (-(long) a)) - counter(-a - 1);
if (b > 0)
ret += counter(b);
else if (b < -1) {
b++;
ret -= ((long32 * (-(long) b)) - counter(-b - 1);
}
return ret;
}

/**
* Calculate the number of 1s from number 0 to number num;
*
* */
public static long counter(int num) {
if (num == 0)
return 0L;
if (num % 2 == 0)
return counter(num - 1) + ones(num);
return (((long) num + 1) / 2) + 2 * counter(num / 2);
}

/**
* Calculate the number of 1s in the number
*/
public static long ones(int num) {
String str = Integer.toBinaryString(num);
long sum = 0L;
for (int i = 0; i < str.length(); i++)
if (str.charAt(i) == '1')
sum++;
return sum;
}
}