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.

Comments

  1. Unknown6:13 AM, November 01, 2012

    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. Unknown7:38 AM, November 01, 2012

    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

Post a Comment

Popular posts from this blog

Fraction Brainteaser

Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20 out of 28 Geometry questions.  In total, Siddhant scores 25 out of 34.  Vaibhav writes another Maths test and correctly answers 20 out of 25 Arithmetic questions and 6 out of 9 Geometry questions. in total, Vaibhav scores 26 out of 34. Note that a) Vaibhav scores more than Siddhant b) Siddhant score better than Vaibhav in both individual topics -  5/6 > 20/25 and 20/28 > 6/9 How is it possible? 
Read more

Buying Dimsums

Source: Alok Goyal (Stellaris VP, Ex-Helion VC) puzzle blog Problem: A fast food restaurant sells dimsums in boxes of 7 and 3. What’s the greatest number of dimsums a person cannot buy. Generalize it for p and q where p and q are relatively prime. I loved the puzzle. Hope you enjoy it too.
Read more

Consecutive Heads

Let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tossing another fair coin, until he get 3 consecutive heads, define Y to be the number of the tosses for this process. 1) Calculate P{X>Y} 2) What's the expected value of X 3) What's the expected value of Y This is probably the hardest puzzle I have ever put on my blog. Hence, I will post its solution in the post directly rather than on comment. Solution: 1) (Solved by me finally after 13 months :)) Make a state diagram. Let the state be (a,b) where a is the number of consecutive heads streak "A" is on currently and b is the number of consecutive heads streak "B" is on currently. So, (0,3) (1,3) are final accepted states and (2,0) (2,1) (2,2) (2,3) are failure states. If you get tails, your contribution to the state reaches to "0" f(State) = P(X>Y | "State" configuration initially)
Read more