2's complement

Problem Links:

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:

import java.io.BufferedReader;
import java.io.InputStreamReader;

/**
 * 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 {
        // BufferedReader br = new BufferedReader(new InputStreamReader(
        // new DataInputStream(new FileInputStream(args[0]))));
        // BufferedWriter bw = new BufferedWriter(new FileWriter(args[1]));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for (int t = 1; t <= T; t++) {
            String[] str = br.readLine().split(" ");
            int a = Integer.parseInt(str[0]);
            int b = Integer.parseInt(str[1]);
            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 = ((long) 32 * (-(long) a)) - counter(-a - 1);
        if (b > 0)
            ret += counter(b);
        else if (b < -1) {
            b++;
            ret -= ((long) 32 * (-(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;
    }
}