从位运算看二进制枚举

位运算符

在C语言中，数据是以二进制存在的，比如2的二进制表示就是10，3的二进制表示就是11……

既然有二进制，那么肯定也有类似于十进制一样的运算方法了。C语言中提供了六种运算符：

解释：

1. 按位与（&）：在二进制的位上，只有两个值都为1，按位与的结果才为1，否则为0，例如 1&1=1（001 & 001），2&1=0（010 & 001）
2. 按位或（|）：在二进制的位上，两个值中任意一个为1，按位与的结果就是1，全为0时结果为0，例如1|1=1（001 | 001 = 001），2|1=3（010 | 001 = 011），0|0=0（000 | 000=000）
3. 按位异或（^）：在二进制位上的值不同时，值为1，否则为0，例如 1^1=0（001 ^ 001= 000），2^1=3（010 ^ 001= 011）
4. 取反（~）：单目运算符，右结合性，即：将每一位上的数字取反，~1=-2 （-010），~0=-1（-001）
5. 左移（<<）：将二进制位上的每一位都向左移动，例如：1<<2=4（001 => 100），左移n位的结果相当于乘以2的n次方，其中（1<<n）可以生成第n位的零，比如1<<15=1000000000000000，后有15个零
6. 右移（>>）: 将二进制位上的每一位都向右移动，例如：4>>2=1（100 => 001），右移n位的结果相当于除以2的n次方

二进制枚举

情景1：

我这里有4个不同的水果，n块钱，每个水果的价格分别为：k1，k2，k3，k4，问：请问我的钱最多能同时买那几个水果？

对于这个情景，因为水果只有4个，所以数据量很小，所以使用暴力枚举法就能过，用两个for循环？不不不，我们使用二进制枚举

首先，1<<4 = 10000（二进制表示），所以1<<4-1=1111（二进制表示）=15（十进制表示），如果从0开始数，则有16个数。我们来看看这16个数：

00 = 0000
01 = 0001
02 = 0010
03 = 0011
04 = 0100
05 = 0101
06 = 0110
07 = 0111
08 = 1000
09 = 1001
10 = 1010
11 = 1011
12 = 1100
13 = 1101
14 = 1110
15 = 1111

我对上面的数据进行了填0处理，以便看的更清晰

我们仔细看看这16个数，你是不是看出一点名堂？如果把每一位上的0或1表示为买或者不买，那么上述的16个数的二进制结果，就表示了这4个水果的所有购买方式！

那么，我们应当如何检索上面的每种可能呢？

前面我们又说到，1<<n可以生成n个0位的数，最前面的为1，例如（1<<4=10000），再利用按位与（&）运算符，就能知道这一位表示的是0还是1

例如，我想知道 2 所代表的二进制位上哪些位为0，哪些位为1，就可以有

for (int j=0;j<n;i++)
{
    if (2&(1<<j))
    {
        printf("%d",j);
    }
}

运行结果为：1，也就是说，只有1号位上为1，其余位置都为0. （2=》0010）

利用这个原理，就可以快速对结果进行遍历了

模板如下：

for(int i=0;i<(1<<n);i++)
{
    for (int j=0;j<n;j++)
    {
        if (i&(1<<j))
        {
            ……
        }
    }
}

例题：

林大oj-和为K