rembocoder's blog

Go through all the supermasks
By rembocoder, history, 5 years ago, translation, In English

In this thread it is shown how to go though all the submasks of a given mask without extra space or time. I needed to do the same thing for the overmasks, but I did not find anything. Based on the formula mask ^ (~mask) = -1, my brother gave me this code:

    for (int over = (1 << n) - 1; over > 0; over = ((over - mask - 1) & ~mask) + mask) {
        cout << over << " ";
    }

It really works. But can I simplify it, so it could be easier remembered during the contest?

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

»
5 years ago, # |
  Vote: I like it +94 Vote: I do not like it 
for (int mask = need; mask < (1 << n); mask = (mask + 1) | need) {

}
→ Reply
»
5 years ago, # |
  Vote: I like it +80 Vote: I do not like it

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

you want the overmasks of $$$S$$$ (i.e.: the masks of which $$$S$$$ is submask). I think it's the same as the NOT ($$$\text{~}$$$) of submasks of $$$\text{~} S$$$. Correct me if I'm wrong.

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

This post has no comment newer than 8 months ago. How did it appear under "Recent actions"?

→ Reply