How many numbers in the given interval with a bit set

Problem: given two numbers a and b find how many numbers with a bit x set are there in the interval [a,b].

Example:

Input: 5 8 2

Output: 3

Explanation:

5 = 0101
6 = 0110
7 = 0111
8 = 1000

The second bit (starting from the least significant bit with index 0) is set only in numbers 5, 6 and 7, so there are 3 numbers in the interval [5, 8] with the second bit set.

Solution:

The naive solution will be to just iterate through all the numbers in the interval and check if the given bit set for each number. If such a bit is set then increment result counter by one. The complexity of this solution is O(n) where n is the size of the interval.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

#include <iostream> #include <chrono> using namespace std; int countNumsWithXBitSet(int l, int r, int x) { int cnt = 0; for (int i = l; i <= r; ++i) { if ((i & (1 << x)) > 0) ++cnt; } return cnt; } int main() { int a, b, x; cin >> a >> b >> x; auto start = chrono::high_resolution_clock::now(); cout << countNumsWithXBitSet(a, b, x) << endl; auto end = chrono::high_resolution_clock::now(); auto duration = chrono::duration_cast<chrono::milliseconds>(end - start).count(); cout << "time: " << duration << " ms" << endl; return 0; }

This solution will work fine if the given interval is rather small (e.g: [0, 1000000]). But it starts taking more time on the larger intervals (e.g.: [0, 1000000000]).

Running the naive solution on my PC gives the following results:

0 1000000 2
500000
time: 6 ms

0 1000000000 2
500000000
time: 2212 ms

There is a much better solution which gives constant time O(1) instead of linear. The traditional trick is to count how many numbers in the intervals [0, b] and [0, a - 1] with a bit set. And the result will be the difference of these counters: count [0, b] - count [0, a - 1].

So, for the given example we will have:

count [0, 8] = 4
count [0, 4] = 1
result = 4 - 1 = 3

Now we need to find the needed counters. Let's consider the interval [0, 8] in binary representation:

3 2 1 0 - bit index (0 is least significant bit)
-------
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0

We can notice that for each bit there is a sequence of 0s, 1s which consists of the segments. The higher bit index, the larger segments:

        0 1 2 3 4 5 6 7 8 - numbers from the given interval
bit 0: 0 1 0 1 0 1 0 1 0
bit 1: 0 0 1 1 0 0 1 1 0
bit 2: 0 0 0 0 1 1 1 1 0
bit 3: 0 0 0 0 0 0 0 0 1

Segments with 1s are marked in bold. Depending on the last number in the given interval we can have all segments full when the last number is a power of two minus one (2 ^ n - 1). If it is not true, then we will also have at most one partial (not full) segment for each bit index. Starts of partial segments are marked in red in the example above.

The length of a full segment: segLen = 2 ^ i, where i - bit index.

The number of full segments: fullSegCnt = (n + 1) / segLen, where n - the last number in the given interval, (n + 1) - the size of the interval [0, n].

Now we can find the total number of 1s in full segments for the specified bit index: onesCnt = (fullSegCnt / 2) * segLen, where (fullSegCnt / 2) - the number of full segments with 1s, we do divide by 2 as for each bit index there will be two groups of segments: the first one with 0s and the second one with 1s.

Ok, what left is to count the number of 1s in the partial segment.

If we give index (starting from 0) to all segments we will notice that all segments with 0s have even index. Having the number of full segments we can check whether the partial segment contains all 1s or not. If the partial segment contains 1s we count the length of this segment and update the total result:

if (fullSegCnt % 2 != 0) onesCnt += (n + 1) % segLen

Now onesCnt contains the total number of 1s for the specified bit index which means the number of numbers in the interval [0, n] with a bit i set.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

#include <iostream> #include <algorithm> #include <chrono> using namespace std; int countNumsWithXBitSet(int l, int r, int x) { if (r == 0) return 0; else if (l == 0) { int segLen = 1 << x; int fullSegCnt = (r + 1) / segLen; int onesCnt = (fullSegCnt / 2) * segLen; if (fullSegCnt % 2 != 0) onesCnt += (r + 1) % segLen; return onesCnt; } else return countNumsWithXBitSet(0, r, x) - countNumsWithXBitSet(0, max(0, l - 1), x); } int main() { int a, b, x; cin >> a >> b >> x; auto start = chrono::high_resolution_clock::now(); cout << countNumsWithXBitSet(a, b, x) << endl; auto end = chrono::high_resolution_clock::now(); auto duration = chrono::duration_cast<chrono::milliseconds>(end - start).count(); cout << "time: " << duration << " ms" << endl; return 0; }

Here're the results:

0 1000000 2
500000
time: 0 ms

0 1000000000 2
500000000
time: 0 ms

Here's a good problem to practice: https://contest.yandex.com/algorithm2016/contest/2540/problems/B/