**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.

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.

ReplyDeleteConsider 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[0],A[1],A[2],...A[31] 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

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.

ReplyDeleteA 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[0],A[1],A[2],..A[30]

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]