Skip to content

Instantly share code, notes, and snippets.

@yuvipanda
Created October 13, 2011 18:51
Show Gist options
  • Star 5 You must be signed in to star a gist
  • Fork 4 You must be signed in to fork a gist
  • Save yuvipanda/1285119 to your computer and use it in GitHub Desktop.
Save yuvipanda/1285119 to your computer and use it in GitHub Desktop.
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
Copy link

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