Блог пользователя skpro19

Автор skpro19, история, 8 лет назад, По-английски

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

  • Проголосовать: нравится
  • +10
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

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).

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится
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)