Hamming weight of an interval

Question

My task is to calculate number of 1-bits of interval [1,10^16]. Loop is obviously unusable for this case, and I've heard there exists an algorithm for this. Can anyone help?

More generally, an algorithm for number of 1-bits in an interval [1,n] would be nice.

If that helps, I figured that number of 1-bits of interval [1,2^n-1], n positive integer, is n*2^(n-1).

Answer 1

1. Let f(A,B) = the number of 1-bits from A to B, including A and B.
2. I figured that too : f(1,2^k-1) = k*2^(n-1)
3. Obviously, f(1, x) = f(0, x) since 0 has no 1-bit.

4. Let's x = 2^k + b, f(1, x) = f(0, x) = f(0, 2^k + b) = f(0, 2^k - 1) + f(2^k, 2^k + b)

   The key problem is f(2^k, 2^k + b)

   2^k = 1 0 0 0 ... 0 0

   2^k + 1 = 1 0 0 0 ... 0 1

   2^k + 2 = 1 0 0 0 ... 1 0

   2^k + 3 = 1 0 0 0 ... 0 1

   ... ...

   2^k + b = 1 0 0 0 ... ? ?

   Clearly, there is 1-bits in the first bit of each number from 2^k to 2^k + b. And there is (b+1) integers from 2^k to 2^k + b.

   We can remove the first 1-bit. And it becomes below.

   0 = 0 0 0 0 ... 0 0

   1 = 0 0 0 0 ... 0 1

   2 = 0 0 0 0 ... 1 0

   3 = 0 0 0 0 ... 0 1

   ... ...

   b = 0 0 0 0 ... ? ?

   So, f(2^k, 2^k + b) = (b+1) + f(0, b).

   f(0, x) = f(0, 2^k - 1) + f(2^k, 2^k + b) = f(0, 2^k - 1) + (b+1) + f(0, b)

   Clearly, we have to recursively calculate f(0,b).

5. Give an example of step 4.

   For f(1, 31) = 80, and 31 has 5 1-bits.

   so f(1, 30) = 80 - 5 = 75;

   Let's calculate f(1, 30) use the method of step 4.

   f(1, 30) = f(0, 30)

   = f(0, 15) + f(16, 30)

   = 32 + 15 + f(0, 14)

   = 47 + f(0, 14)

   = 47 + f(0, 7) + f(8, 14)

   = 47 + 12 + 7 + f(0, 6)

   = 66 + f(0, 6)

   = 66 + f(0, 3) + f(4, 6)

   = 66 + 4 + 3 + f(0, 2)

   = 73 + f(0, 2)

   = 73 + f(0, 1) + f(2, 2)

   = 74 + f(2, 2)

   = 74 + 1 + f(0， 0)

   = 75

Answer 2

The number of 1-bits in interval [1,n] is the number of 1-bits in interval [1,2^m] plus the number of 1-bits in interval [1,n-2^m] plus n - 2^m.

m is ⌊log(n)/log2⌋.