Fast bit counting in range

Question

I need to find the algorithm solving this problem :
find the sum of all positive bits in numbers in range [x,y].
Warning : x and y can be very big ( from 1 to 10^20 ).
Thanks for help.

Hint: find the number of '1' bits in the rightmost position. — wildplasser, Jun 21 '12 at 18:38
Is this homework? What have you tried already? What aspect of the problem are you stuck on? — hatchet - done with SOverflow, Jun 21 '12 at 18:48
possible duplicate of [Number of 1s in the two's complement binary representations of integers in a range](http://stackoverflow.com/questions/7942732/number-of-1s-in-the-twos-complement-binary-representations-of-integers-in-a-ran) — tskuzzy, Jun 21 '12 at 19:02
i have got some brute versions of algorithm. Im using __builtinpop_count() for every element and adding it to sum variable. — John Smith, Jun 21 '12 at 19:04
This problem is equivalent to the one stated on [this other post](http://stackoverflow.com/questions/11156876/given-a-number-n-find-out-how-many-numbers-have-digit-2-in-the-range-0-n) (and that I have just replied :-) ) — salva, Jun 23 '12 at 07:48

score 3 · Answer 1 · answered Jun 21 '12 at 19:56

It may be instructive to look at a concrete example to identify patterns. For example, 20 to 25. Here are their binary representations:

Looking at it by column, it's apparent that the rightmost column always alternates between 0 and 1. From this we can conclude that if your range has N numbers in it and N is even, then the rightmost column has N/2 bits in it. Now disregard the rightmost column and try to identify a pattern in the remaining bits.

Each number in the list repeats itself exactly once. Converting to decimal, we see that these numbers are 1010 = 10, 1011 = 11, 1100 = 12. Using these two observations, we can conclude that bitsInRange(20, 25) = (27 - 20 - 1) + 2*bitsInRange(10,12). Both of the patterns we identified are true for any even start number and odd end number, so the formula can be generalized to:

bitsInRange(X,Y) =
if X is even and Y is odd:
    (Y - X - 1) + 2*bitsInRange(X/2, (Y-1)/2)

But what if we have a start number that's odd, or an end number that's even? The above formula won't work for those, because the two patterns we identified aren't precisely the same for those kinds of numbers. You could try writing seperate formulas for each possible combination of even and odd, but that way is perilous and full of Fencepost Errors. You'll have an easier time if you take advantage of these critical properties:

bitsInRange(X, Y) = bitsInRange(X, Y-1) + numBits(Y)
bitsInRange(X, Y) = bitsInRange(X+1, Y) + numBits(X)

... Where numBits gives the quantity of 1 bits in a single number.

Now we can write a recursive formula for every possible combination of even and odd ranges. (We also need a base case, by the way)

function bitsInRange(X,Y):
    if X == Y:
        return numBits(X)
    if X is odd:
        return bitsInRange(X+1, Y) + numBits(X)
    if Y is even:
        return bitsInRange(X, Y-1) + numBits(Y)
    return (Y - X - 1) + 2*bitsInRange(X/2, (Y-1)/2)

Because the final case chops the problem space in half, and all the other cases quickly transform the problem into the final case, the whole formula has logarithmic complexity. This is good if you're trying to get the bits in a huge range like [1, 10^20]. Even for huge numbers like that, bitsInRange will only run about 200 times or so.

Fast bit counting in range

1 Answers1