Lets take an example of the range of N=32 bits
2^32 = 4294967296
00000000000000000000000000000000
00000000000000000000000000000001
00000000000000000000000000000010
00000000000000000000000000000011
...
11111111111111111111111111111100
11111111111111111111111111111101
11111111111111111111111111111110
11111111111111111111111111111111
Now lets consider a subset within this range whose consecutive 0s can be 0 to maximum 3 0s.
The following are examples of valid and invalid subsets -
Valid subset (consecutive 0s - 0 to maximum 3):
00100100100100100100100100100101 - (subset 0)
10101010101010101010101010101010 - (subset 1)
10010010010010001000100010101111 - (subset 2)
11011001000111101000100010010011 - (subset 3)
...
11111111111111111111111111111111 - (subset S max value)
So, count(valid subset) < 2^32
Invalid subset (at least 1 consecutive 0s > 3):
10000111111111111111111111111001
10101010100000000001111000100111
11111111101010101010101010000001
10000000000000001111010100010101
...
I have the following queries -
- How to find the total count of valid subsets for a given value of N (ex. 2^32, 2^40, 2^64 etc)
- How to dynamically generate the subset value for each matching subset, in an incremental manner, for a given value of N (ex. 2^32, 2^40, 2^64 etc)
So, for N=32,
If the value is "00100100100100100100100100100101", then subset value "0" must be dynamically generated
If the value is "10101010101010101010101010101010", then subset value "1" must be dynamically generated
If the value is "10010010010010001000100010101111", then subset value "2" must be dynamically generated
If the value is "11011001000111101000100010010011", then subset value "3" must be dynamically generated
If the value is "11111111111111111111111111111111", then subset value "subset S max" must be dynamically generated
- Consecutively, given the subset value, the bit value must also be dynamically generated
So, for N=32,
If subset value is "0", then bit value "00100100100100100100100100100101" must be dynamically generated
If subset value is "subset S max", then bit value "11111111111111111111111111111111" must be dynamically generated
and so on...
The main point is dynamically generating the values, so they are not required to be stored; this is feasible for large values of N (ex. 2^32, 2^40, 2^64 etc and greater)