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

1

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?

2012-04-03 22:27
by bl3e
Check my answer here for example - Daniel Fischer 2012-04-03 22:35
Have you looked at <code>std::bitset</code> - Peter Wood 2012-04-03 23:12

0

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)`.

2012-04-03 22:54
by Daniel Fischer