Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)

Oct 21, 2012

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.

2 comments:

  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[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

    ReplyDelete
  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[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]

    ReplyDelete