Create a gist now

Instantly share code, notes, and snippets.

2's Compliment Solution (InterviewStreet CodeSprint Fall 2011)

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.

#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 ;
}
@mayurarora

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment