Counting 1s in the two's complement representations of integers in range[x,y]

Question

My question is related to a previous question in the forum - Number of 1s in the two's complement binary representations of integers in a range There was no 'add comment' for me.So i am asking it here The question was to count the number of 1's in writing down all numbers in 2's complement form,which are in a range specified by two input numbers The solution is posted at https://gist.github.com/1285119 It is as below

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) ;
  }


 long long solve(int a,int b)
 {
  if(a >= 0)
  {
   long long ret = solve(b) ;
   if(a > 0) ret -= solve(a - 1) ;
   return ret ;
   }
 long long ret = (32LL * -(long long)a) - solve(~a) ;
 if(b > 0) ret += solve(b) ;
 else if(b < -1)
 {
  b++ ;
  ret -= (32LL * -(long long)b) - solve(~b) ;
 }
return ret ;
}

When the input is 4 //No of test cases

-1 //first number -2 //Second number Output 0

-1 -3 Output -31

-3 -5 Output -30 //how can number of 1's be -30

1 2 Output 2

Since the code is posted as Codesprint solutions on InterviewStreet and a highly voted answer on this forum.It should have been correct. Can anyone explain the logic behind the line long long ret = (32LL * -(long long)a) - solve(~a) in solve(int a,int b) And what is the purpose of #define INF (int)1e9 //setting value of infinity when not using it?

Check [my answer here](http://stackoverflow.com/a/9660937/1011995) for example. — Daniel Fischer, Apr 03 '12 at 22:35
Have you looked at [`std::bitset`](http://en.cppreference.com/w/cpp/utility/bitset)? — Peter Wood, Apr 03 '12 at 23:12

score 0 · Accepted Answer · answered Apr 03 '12 at 22:54

The wrong results for your inputs

-1 -2
-1 -3
-3 -5

are because the programme assumes that the two limits are entered in ascending order and does no checks, therefore input not conforming to that expectation produces wrong results. A simple

if (b < a) {
    int temp = a;
    a = b;
    b = temp;
}

at the beginning of int solve(int a, int b) would make it return the correct result for input in any order.

The logic behind long long ret = (32LL * -(long long)a) - solve(~a) is that (in twos' complement) the bitwise complement of n is ~n = (-n)-1. The total number of bits (0 or 1) in the numbers from a to -1 - both inclusive - is 32 * |a| if a < 0. From that count, we subtract the total number of 0 bits in these numbers, which is the total number of 1-bits in their bitwise complements. These bitwise complements are the numbers from 0 to |a| - 1 = ~a, both inclusive, the count of 1-bits among these is given by solve(|a| - 1) = solve(~a).

Counting 1s in the two's complement representations of integers in range[x,y]

1 Answers1

Linked