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

Sample Input:

-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

Marc Gravell
  • 1,026,079
  • 266
  • 2,566
  • 2,900
user3164808
  • 11
  • 2
  • Quick... anyone answer this question with logic? – user3164808 Jan 06 '14 at 09:18
  • 5
    just answer as best you can; interviews are usually just as much about how you think - and if I caught an interviewee of mine asking the interview question on the internet.... bad things. Worst case you need 2 things; a for loop, and a "count the bits" method... If there is a better case: great – Marc Gravell Jan 06 '14 at 09:19
  • If these are the kind of interview questions out there for a development position I'd probably fail. I've lost touch of bits and bytes over the years, quite embarrassing really. –  Jan 06 '14 at 09:29
  • @MarcGravell i agree with what you say, and in case should we help him with this? i'm not downvoting the question but i don't think we should help him if we don't like out interviewees ask interview questions on internet and get helped. – Saro Taşciyan Jan 06 '14 at 09:32
  • @Zefnus: Why not? It proves that he knows how to find answers on the internet and on SO in particular, which is a very important "programming tool" nowadays. I use it almost every day at work myself... – barak manos Jan 06 '14 at 09:36
  • Hint: http://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer – Marc Gravell Jan 06 '14 at 09:37
  • 1
    @barakmanos We all use SO everyday at work. But i'm sure you are not asking a question posting all your analysis and throwing it to our head waiting for people to do your work while you sit. Not all kinda of requests has an answer in SO, questions like this or "do my work", "do my homework", "do my project" isn't supported here as far as i know – Saro Taşciyan Jan 06 '14 at 09:42
  • 1
    @Zefnus, I agree on that one... – barak manos Jan 06 '14 at 09:51

1 Answers1

1
for (int i=1; i<line[0]; i++)
{
    int numOf1s = 0;
    for (int j=line[i].A; j<=line[i].B; j++)
    {
        for (unsigned int n=j; n>0; n>>=1)
            numOf1s += n & 1;
    }
    printf("%d\n",numOf1s);
}
barak manos
  • 29,648
  • 10
  • 62
  • 114