从二进制枚举看位运算#

位运算符#

在计算机中，一切的数据都是以二进制的形式存在的，数字也不例外，例如，数字 2 的二进制表示就是 010，数字 3 的二进制表示就是 011，以此类推。

既然有二进制，那么肯定也有类似于十进制一样的运算方法了。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，问：我的钱最多能同时买那几个水果？

首先我们分析下，由于水果的种类是已知的，并且每个种类只有买或者不买两种情况，那么我们可以假设 1 为买这种水果，0 为不买这种水果，那么如果我们只买第 1 个水果，就可以表示为 0001（从右往左数，从1开始），同理，如果我们只买 第 2 种水果，就是 0010，如果要同时买 1 和 2 ，那就是 0010，怎么样，是否发现端倪了？ 0001 不就是代表十进制的 1 么？ 0010 不就是十进制的 2 么？ 那么如果要涵盖所有的购买情况，是否意味着只需要枚举 0000 到 1111 所有的情况，我们就可以以此计算出答案了呢？

说做就做，我们先生成所有的情况

for (int i = 0; i < (1<<4) /* 0x1111 */ ; i++) {
	// ...
}

接下来我们要做的就是校验哪一位是 1:

// i 为 我们要校验的数据
// j 为 我们要查看的位，从 0 开始
if (i & (1 << j)) {
	// ...
}

那么我们就有模板：

for (int i = 0; i < (1<<4) /* 0x1111 */ ; i++) {
	if (i & (1 << j)) {
		// 这里是买的情况
		// 我们统计这里买的情况，然后计算买的物品的价值总和与物品数量
		// 得到的最大物品数量就是我们要的答案了
	}
}

例题：#

林大oj-和为K