2's Compliment Solution (InterviewStreet CodeSprint Fall 2011)

Hint.md

The number of 1's in the range 0..X (X is positive) is easy to calculate (Can you get a simple recurrence which does this in O(log X) ?) Another observation is that the number of 1's in -X is equal to the number of 0's in ~(-X) = X - 1. Using this, it is easy to calculate the answer for negative ranges as well.

problemsetter.cpp

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std ;
#define INF (int)1e9

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

int main()
{
 int runs,a,b ;
 cin >> runs ;
 while(runs--)
 {
  cin >> a >> b ;
  long long ret = solve(a,b) ;
  cout << ret << endl ;
 }
 return 0 ;
}

How many 1's do we have in the 2's compliment of 1 (using 32 bits) ?