Skip to content

@yuvipanda /Hint.md
Created

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
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
Something went wrong with that request. Please try again.