Counting the numbers between 1 and N (inclusive) where the i-th bit is set

Question

I want to count how many integers between 1 and N have their ith bit set. For example, if N = 10 and i = 0, then the result should be 5 (because 1 = 0001₂, 3 = 0011₂, 5 = 0101₂, 7 = 0111₂, and 9 = 1001₂ each have a 1 at bit 0).

The naive linear-time solution is to iterate from 1 to N and, for each number, see if it has its ith bit set.

A slightly better approach would be that because for a known power of 2 (say 2^x), 2^x−1 numbers will have their ith bit set till the number 2^x − 1, where 0 ≤ i < x. So calculate all the numbers with their ith bit set starting from (N − 2^x), where N is the number till we seek to find all the numbers with their ith bit set and 2^x is the nearest power of 2 for the number N. This approach decreases the number of iterations but is still a linear-time solution and can in some cases be very useless for higher numbers.

Is there a constant-time solution?

Answer 1

Let us first take a look at an example. If we set n=10, and we look at the second bit, so k=1 from the right, we see:

0000    0
0001    0
0010    1
0011    2
0100    2
0101    2
0110    3
0111    4
----
1000    4
1001    4
1010    5

We here see that there are ⌊N/2^k+1⌋ full round trips of the k-th bit, and each such round trip results in 2^k set bits. We grouped these entries before the horizontal bar.

Furthermore there are then still N + 1 - 2^k+1×⌊N/2^k+1⌋ entries under the horizontal bar. We know for sure that this is less than 2^k, since otherwise ⌊N/2^k⌋ would be one higher. The first 2^k-1 entries have 0 as selected bit, whereas the remaining bits (at most 2^k-1 entries) have 1 as selected bit.

We can thus construct the following algorithm in Haskell:

countBit k n = c1 +  max 0 (n + 1 - c0 - sk)
    where sk = shiftL 1 k
          c1 = shiftL (shiftR n (k+1)) k
          c0 = shiftL c1 1

For example for k=1, we obtain the following counts:

Prelude Data.Bits> map (countBit 0) [0..32]
[0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13,14,14,15,15,16,16]
Prelude Data.Bits> map (countBit 1) [0..32]
[0,0,1,2,2,2,3,4,4,4,5,6,6,6,7,8,8,8,9,10,10,10,11,12,12,12,13,14,14,14,15,16,16]
Prelude Data.Bits> map (countBit 2) [0..32]
[0,0,0,0,1,2,3,4,4,4,4,4,5,6,7,8,8,8,8,8,9,10,11,12,12,12,12,12,13,14,15,16,16]
Prelude Data.Bits> map (countBit 3) [0..32]
[0,0,0,0,0,0,0,0,1,2,3,4,5,6,7,8,8,8,8,8,8,8,8,8,9,10,11,12,13,14,15,16,16]
Prelude Data.Bits> map (countBit 4) [0..32]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,16]

So for n=10 and k=1, we get the expected:

Prelude Data.Bits> countBit 0 10
5
Prelude Data.Bits> countBit 1 10
5

Or we can count the number of set bits with column k=3 for numbers from 0 to 12345 (inclusive) with:

Prelude Data.Bits> countBit 3 12345
6170

or for k=15 and n=12'345'678'901'234'567'890

Prelude Data.Bits> countBit 15 12345678901234567890
6172839450617282560

and for n=123'456'789'012'345'678'901'234'567'890:

Prelude Data.Bits> countBit 15 123456789012345678901234567890
61728394506172839450617282560

We here perform some bitshifts and subtractions, for large numbers, these can be done in O(log N) time (with N the value of the upperbound).