CODEWITHSUNDEEP
bitmask
Krzysztof Lewko
Krzysztof Lewko

Reputation: 1002

Generating binary numbers with length n with same amount of 1's and 0's

Question same as in the title. I've done two approaches. One is straightforward. Generate all bitmasks from

2^{n-1}

to

2^n

And for every bitmask check if there is same amount 1's and 0's, if yes, work on it. And that's the problem, because i have to work on those bitmasks not only count them.

I came with second approach which runs on O(2^{n/2}) time, but seems like it's not generating all bitmasks and i don't know why.

Second approach is like that : generate all bitmasks from 0 to 2^{n/2} and to have valid bitmask( call it B ) i have to do something like this : B#~B

where ~ is negative.

So for example i have n=6, so i'm going to generate bitmasks with length of 3.

For example i have B=101, so ~B will be 010 and final bitmask would be 101010, as we see, we have same amount of 1's and 0's.

Is this method good or am i implementing something bad ? Maybe some another interesting approach exist? Thanks

Chris

Upvotes: 0

Views: 640

Answers (2)

supercat
supercat

Reputation: 81179

It's possible, given a binary number, to produce the next higher binary number which has the same number of 'ones', using a constant number of operations on words large enough to hold all the bits (assuming that division by a power of two counts as one operation).

Identify the positions of the least significant '1' (hint: what happens if you decrement the number) and the least significant '0' above that (hint: what happens if you add the "least significant 1" to the original number?) You should change that least significant '0' to a '1', and set the proper number of least-significant bits to '1', and set the intervening bits to '0'.

Upvotes: 0

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726619

Try a recursive approach:

void printMasks(int n0, int n1, int mask) {
    if (!n0 && !n1) {
        cerr << mask << endl;
        return;
    }
    mask <<= 1;
    if (n0) {
        printMasks(n0-1, n1, mask);
    }
    if (n1) {
        printMasks(n0, n1-1, mask | 1);
    }
}

Call printMasks passing it the desired number of 0's and 1's. For example, if you need 3 ones and 3 zeros, call it like this:

printMasks(3, 3, 0);

Upvotes: 2

Related Questions