状压 dp

套路

int count(unsigned x)
{
    int ret;
    for (ret = 0 ; x ; x &= (x - 1)) ret++;
    return ret;
}

1
2
3
4
5
6

for (unsigned t = s ; t ; t = (t - 1) & s)
{
    /* do something on t */
}

1
2
3
4

假设全集状态为 u，且 s 是 f 的一个子集.

for (unsigned t = (f ^ s) & u ; t ; t &= (t - 1))
{
    unsigned bit = t & -t;
    /* do something on bit */
}

1
2
3
4
5