Binary Filter

Have you ever wondered how the sequence of natural numbers looks like if you filter out all the numbers that don't match a given number of ones or zeros in its binary representation? Well, i did, a while ago and that's why i came up with this little piece of code, the Binary Filter. Although it may not seem like it, the solution for this particular problem was somewhat tricky to obtain, hence i decided to share it with the world.

The key idea to my solution is the observation that the problem "Give me all numbers with \(k\) ones in its binary representation" is very similar to calculating the binomial coefficient. Consider the following table containing all 5 digit numbers with 3 ones.

:: TABLE BLOCK ::

\(i\)	\(N_{10}\)	\(N_2\)
0	28	11100
1	26	11010
2	25	11001
3	22	10110
4	21	10101
5	19	10011
6	14	01110
7	13	01101
8	11	01011
9	7	00111

Listing: A - "Binary Filter in action"

Naturally, the number of items equals the binomial coefficient 5 over 3.
In order to calculate the correct number at an index \(i \in [0,9]\), we need to know how many ones are at the top and how many zeros are at the bottom for the first column. This happens to be the quotient of \(3 \over 5\) times the binomial coefficient 5 over 3. This is true for any combination of \(n\) and \(k\). Finally, after knowing whether we're in the upper or lower half of the table, we can dismiss the first column and analyze the remaining \(n-1\) columns.

The Code

As usual, here the necessary code snippets for your own project. You're going to need an implementation of the binomial coefficient. Instead of using the standard version, you might want to use this optimized version without explicitly calling the factorial function.

:: CODE BLOCK ::

int binomial(int _n, int _k)
{
    if(_k < _n-_k) _k = _n-_k;
    int c = 1;

    for(int i=0; i<_k; ++i){
        c = c*(_n-i);
        c = c/(i+1);
    }

    return c;
}

Listing: B - "Binomial Coefficient"

And finally the actual binary filter function in a recursive implementation. The function will return the \(i\)-th, \(n\) digit number with \(k\) ones in its binary representation. The order of values is descending.

:: CODE BLOCK ::

int bfilter(int _n, int _k, int _i)
{
    if(_n < =0) return 0;

    //Number of "1"s
    int n_x = (_k*binomial(_n, _k))/_n;

    //_i is in "1" block
    if(_i < n_x){
        return pow(2, (_n-1)) + bfilter(_n-1, _k-1, _i);
    }
    //_i is in "0" block
    else{
        return bfilter(_n-1, _k, _i-n_x);
    }
}

Listing: C - "Binary Filter"

Check out the ▷docs for further information.