michaellin250's blog

By michaellin250, history, 6 weeks ago, In English,

Everytime I do a contest that has a problem involving bitmasking, I never know it was a bitmasking question. They would end up using bitmasking in a way such as brute forcing a solution. For the problems that do involve bitmasking, it seems like the editorial just pulled random masks out of thin air, like x >> i & 2 etc, etc. I understand the basics of bitmasking such as what >> and << means and what & 1 means. But I don't understand how to actually come up with these mask solutions because they seem like voodoo magic at the moment where the solution just comes up. How do you actually learn how to solve bitmasking questions? Do you just draw out the binary representation of every number and hopefully find something??

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

»
6 weeks ago, # |
  Vote: I like it +22 Vote: I do not like it

I think many people have the same problem. Would be great if someone suggested a few standard/good problems to familiarize with bitmasking concepts.

»
6 weeks ago, # |
  Vote: I like it +63 Vote: I do not like it

Don't think about them as bitmasks, think about them as sets. Often bitmasks are just used as a nice notation/representation of sets.

For example the number (written in binary) $$$101100101_2$$$ just represents the set $$$\{0, 2, 5, 6, 8\}$$$ (I count positions from the right and put a number in the set only if there is an 1 in that position).

As a typical example, the traveling salesman problem can be solved with DP, states like $$$\mathrm{dp}[\mathrm{mask}][k]$$$, where $$$k$$$ is the last visited vertex and $$$\mathrm{mask}$$$ is some bitmask. This bitmask can seem like a mysterious object but if you think about it as a set, it's just the set of already visited vertices.

Let's see what these weird things like x >> i & 2 mean in terms of sets (work examples of these on paper out if you don't "get" them).

  • x & y is the intersection of sets $$$x$$$ and $$$y$$$;
  • x | y is the union on sets $$$x$$$ and $$$y$$$;
  • 1 << k is the set $$$\{k\}$$$ (one-element set consisting only of $$$k$$$);
  • (x >> k) & 1 is 1 if $$$k \in x$$$, 0 otherwise.

Things are a bit different with XOR (you can think of it as symmetric difference but it's not so helpful). Many problems about XOR are actually problems about linear algebra, you can read about it here.