Instantly share code, notes, and snippets.

# yuvipanda/Hint.md Created Oct 13, 2011

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 #include #include 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 commented Oct 28, 2012

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