Effective bit-on in counting the number of case

Question

I am wondering the way of bit-on in counting the number of case.

SITUAITION

check the whole possible n/2 cases of n.

MY APPROACH

bool possible(int state)

it is the function for counting '1' in the state. if cnt is equal to n/2 return true, or return false.

inline bool possible(int state){
    int cnt=0;
    for(int t=1;;t*=2){
        if(t==(1<<n)) break;
        if(cnt>n/2) break;
        if((t&state)==t) ++cnt;
    }

    if(cnt==n/2) return true;
    else return false;
}

void query()

it searches all possible states.

inline void query(){
    int tar=n/2;
    int ss=(1<<tar)-1;
    int ee=(1<<n)-1;
    for(int i=ss;i<=ee;++i){
        if(possible(i)) process(i);
    }
}

I want to use bitmask for solving the whole possible n/2 cases of n. But I think query() function is ineffective, because it searches the whole cases. Is there any effective way to approach this problem?

THE MEANING OF BIT-ON

for example, if n=4, then we have to bit-on two index, in 0-based index,

0001 [fail]

0010 [fail]

0011 [indices of 0,1 bit-on]

0100 [fail]

0101 [indices of 0,2 bit-on]

0110 [indices of 1,2 bit-on]

0111 [fail]

1000 [fail]

1001 [indices of 0,3 bit-on]

1010 [indices of 1,3 bit-on]

1011 [fail]

1100 [indices of 2,3 bit-on]

1101 [fail]

1110 [fail]

1111 [fail]

---

Apparently, 4C2=6 cases selected, so the states,

[0011, 0101, 0110, 1001, 1010, 1100] will be searched.

Answer 1

The problem can be solved recursively

• first you choose the position of your left-most "1"
• then call the function recursively to place the remaining "1"s
• the recursion ends when there are no "1"s left to place

That means you need to define a more general function that generates k "1"s in a n bit number.

A handy trick to avoid returning and processing subresults is passing an accumulator down. You can than call your process() function deep down in the recursion.

Example code in python. Should translate to C easy enough.

def process(i):
    '''prints decimal and binary representation of i'''
    print(i, bin(i))

def helper1(length, ones, acc):
    if ones == 0:
        process(acc)
    else:
        for i in range(ones-1, length):   # iterates from ones-1 to length-1
            helper1(i, ones-1, acc | (1<<i))

def solution1(n):
    helper1(n, n >> 1, 0)

On a modern CPU this should run just fine. It can be "improved" though by using bitmasks instead of indices as parameters. However, the code gets harder to understand.

def helper2(first_mask, last_mask, acc):
    if last_mask == 0:
        process(acc)
    else:
        mask = last_mask
        while mask <= first_mask:
            helper2(mask >> 1, last_mask >> 1, acc | mask)
            mask = mask << 1

def solution2(n):
    helper2(1 << (n-1), 1 << (n//2 -1), 0)

• first_mask represents the left-most position where a "1" can be inserted
• last_mask represents the right-most position where a "1" can be inserted (so that there is still enough room for the remaining "1"s). It doubles as a counter for remaining "1"s.

Bit-twiddling-hack

It just occured to me that you can also solve the problem without recursion:

Start with the smallest number and find the next greater number in a loop. To find a greater number you need to move a "1" to the postion of the next "0" to the left and then move all "1"s that are on the right of your new "1" the very right.

While this sounds complicated it can be done fast using bit-twiddling-hacks.

def helper3(total, ones):
    if ones == 0:
        process(0)
        return
    i = (1 << ones) - 1
    while i < (1 << total):
        process(i)
        last_one_mask = (((i - 1) ^ i)  >> 1) + 1
        temp = i + last_one_mask
        i = temp | (((temp ^ i) // last_one_mask) >> 2)

def solution3(n):
    helper3(n, n >> 1)

If your language has constant width integers you could get an overflow when calculating temp. To avoid bad behaviour you must abort the loop if temp<i.