### Number of 1s in 2's complement representation

Source: Interview Street CodeSprint (slightly modified)

Problem:
One of the basics of Computer Science is knowing how numbers are represented in 2's complement. Imagine that you write down all numbers between A and B inclusive in 2's complement representation using 32 bits. How many 1's will you write down in all ?

Input:
Two integers A and B

Output:
The number of 1s

Constraints:
-2^31 <= A <= B <= 2^31 - 1

Find the asymptotically optimal algorithm.

1. Consider the representation of a number -n in two's complement. We traverse from right to left in binary representation of n and once we see a 1 we flip the bit values of all the positions to the left of it.

Consider the two numbers -k and -(2^n+k) 0<=k<2^n
The number of the 1's in two's complement of both numbers is going to differ by just 1. just the (n+1)th bit of -(2^n+k) is going to be 0.
If f(x) is number of 1's in two's complement of -x then we have the following relation
f(2^n+k) = f(k) - 1;
Hence sum(f(2^n+k)) = sum(f(k)) - k;

Pre-compute the values of sums for various powers of 2 based on simple modification of the previous relation
we have sum(f(2^k)) = 2*sum(f(2^(k-1)) - 2^(k-1)
We have the values for -1,-2,-2^2,-2^3,...,-2^31 stored in A,A,A,...A respectively

Now we can recursively compute the value of sum(f(x)) for any x using our original relation

sum(f(x))=
if x == 0 then 0
if x is a power of 2 A[log2(x)]
otherwise A[y] + computeNeg(n - 2^y) - (n - 2^y)

where y is the largest power of 2 that is less than x

note that all sums range from 0 to -x. With this we are good to answer for and A<=0 and B<=0.

We will be able to compute the required value for any A and B if we are able to sum from 0 to any positive number. Instead of forming a similar sequence we can use the fact that Number of 1's in a number n is equal to the number of 0's in two's complement of -(n+1). So for any n the value will be (32*n - sum(f(n+1)) + 32 where sum(f(n)) is the quantity described previously

2. I have complicated up the explanation very much in the previous post, though what I mentioned there works it is quite a round about way of doing things. Here is a much straight forward way of doing it.

A positive number in two's complement is same as its normal binary representation. We will first solve for finding the total number of 1's for numbers in range [0,X].

consider the way we construct numbers in binary format in increasing order.

{0,1},{10,11},{100,101,110,111},{1000,1001,1011,1100,1101,1110,1111},....

Here we have grouped the numbers based on the position of the most significant bit.

In each group (exclusig the first) there are 2,4,8,16,.. elements and last element of a group is 2^{n}-1 where n is its group number

The numbers in one particular group-m are obtained by using all the elements from previous groups and setting the mth-bit to one.

So if f(x) = total number of 1's in all numbers between in the range [0,x]. Then for a particular group m's last element we have

f(2^{m} - 1) = 2*f(2^{m-1} - 1) + 2^{m-1}

2^{m} has only one 1 in its binary rep hence f(2^{m}) = f(2^{m-1})+1

By this we have f(2^{m}) - 1 = 2*(f(2^{m-1}) - 1) + 2^{m-1}

f(2^{m}) = 2*f(2^{m-1}) + 2^{m-1} -1 This has a closed form solution m.2^{m-1}+1

Either using the recursion or the closed form compute the values f(1),f(2),f(2^2),f(2^3),...f(2^30) and store them in an array A,A,A,..A

We have now computed the value of f(X) when X is a power of 2 when X is not a power of 2 we can compute it as follows.

X must belong to some kth group. The first element of the group is 2^k we know the value f(2^k). If there are l elements after 2^k they have to be be 2^k+1,...,2^k+l. All we need to find is the number of 1's in these numbers. If we remove the most significant bit in them we have the set {1..l}. So we get the simple recurrence

f(2^k + l) = f(2^k) + f(l) + l = A[k] + f(l) +l
This can computed using a simple recursive program.

Let g(x) = Number f 1's in twos complement of all numbers in range [x,0] where x is a negative number.
Using the fact that Number of 1's in a number n is equal to the number of 0's in two's complement of -(n+1)
we have g(x) = 32*(-x) - f(-(x+1)) since we are dealing with 32 bit numbers

Using f and g we can compute the required value for any range [A,B]