Number of 1s in 2's complement representation

Source: Interview Street CodeSprint (slightly modified)

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 ?

Two integers A and B

The number of 1s

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

    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.


    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]


Post a Comment

Popular posts from this blog

Asking a girl out

Coins Puzzle

Consecutive Heads