skpro19's blog

Generate all the submasks for a given mask ?

By skpro19, history, 9 years ago, In English

How do I generate all the submasks for a given mask?

  • Vote: I like it
  • +10
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by skpro19 (previous revision, new revision, compare).

→ Reply
»
9 years ago, # |
  Vote: I like it +22 Vote: I do not like it

The easiest way I know is:

for(int submask = mask; submask; submask = (submask - 1) & mask) {
         // do something
}

If you want 0 as a submask:

for(int submask = mask; ; submask = (submask - 1) & mask) {
         // do something

        if(submask == 0) break;
}

You have to know if we want to do something with the submasks of every mask till 2^N the time complexity will be O(3^N) not O(4^N).

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it 
void rec(int start,int fin,int mask)
{
    if(start==finish)
    {
        // masks have been generated evaluate them
        return;
    }
    rec(start+1,fin,mask);
    if(mask&(1<<start))
    {
        rec(start+1,fin,mask+(1<<start));
    }
}
 if you want  to generate masks for an n bit number call rec(0,n,0).

Time complexity = O(3^n) if we are generating all submasks for all 2^n numbers for the n bit number else for a particular number having k out of n bits set complexity is O(2^k)

→ Reply