How to find number of integers in a given range has even set bits

Here's a key fact:

• If n is a non-negative even number, then exactly half of the non-negative integers less than n have even parity and the other half have odd parity. ("Even parity" means that the number of bits in the binary representation is even.)

Suppose we need to count the number of integers in the range [l, r) with some property P, and we know how to solve this problem for any range where l is 0. ( "[l, r)" is a "half-open range": all integers n where l≤n<r. That makes the arithmetic easier.) Then we just need to subtract in order to solve the general problem where l≠0: COUNT[l,r) = COUNT[0,r) − COUNT[0,l).

The first fact doesn't quite tell us all we need to know, since it only works for even n. But if n is odd, n-1 is even, and all we need to do is check the parity of n-1 itself, which is the extra number not in the range [0,n-1).

Putting all that together, if we have the range [l, r), we compute the count as follows:

• COUNT(0,l) is l/2 if l is even, and (l-1)/2+PARITY(l) if l is odd
• COUNT(0,r) is r/2 if r is even, and (r-1)/2+PARITY(r) if r is odd
• COUNT(l,r) is COUNT(0,r) − COUNT(0,l)

That last computation requires at most two parity computations, regardless of how large the range is, as well as a couple of divisions and a subtraction.

If this were a mathematics site, I might feel compelled to prove the assertion in the key fact at the beginning, but since this is CS I will content myself with a proof outline. We first note that if i is even, then PARITY(i) and PARITY(i+1) are different (since the binary representations only differ in the last bit). Conversely, if i is odd, then PARITY(i) and PARITY(i-1) are different. Now, take all the integers in [0,n) and divide them into the set of integers with odd parity and the set with even parity, and consider the homomorphism

f(i)⇒i+1 if i is even;
f(i)⇒i−1 if i is odd;

The image of f over one of the two subsets of [0,n) is the other subset, since the parity of f(i) is different from the parity of i. So the two subsets are the same size.