位运算

一.核心思想：程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算就是直接对整数在内存中的二进制位进行操作。

二.常见的位运算符

C++ 提供了按位与（&）、按位或（| ）、按位异或（^）、取反（~）、左移（<<）、右移（>>）这 6 种位运算符。这些运算符只能用于整型操作数，即只能用于带符号或无符号的 char、short、int 与 long 类型。

1.按位与（&）

用法：a&b(其中a,b为两个整型类型的数值，如果a和b都为1则整个表达式的值为1否则为0）
例如：3&5 怎么来理解呢？
第一步：把3和5转化为各自的二进制表示。3为11，5为101。
第二步：将位数少的补齐多余位。3为11只有两位二进制数，5为101是三位
	   二进制数。我们将11补齐三位为011。
第三步：将其一一对应。
	   3：011
	   5：101
     结果：001
     001的十进制表示为1。故答案为1。

&运算符在算法竞赛中的一些小技巧：
（1）判断是不是偶数：常规写法 if(n % 2 == 0) 可以换为 if(n & 1 == 0)
别的过于鸡肋，就不在这里赘述了。

2.按位或（|）

用法：a|b(其中a,b为两个整型类型的数值，如果a或b只要有一个或同时为1则整个表达式的值为1否则为0）
例如：3|5 怎么来理解呢？
第一步：把3和5转化为各自的二进制表示。3为11，5为101。
第二步：将位数少的补齐多余位。3为11只有两位二进制数，5为101是三位
	   二进制数。我们将11补齐三位为011。
第三步：将其一一对应。
	   3：011
	   5：101
     结果：111
     111的十进制表示为7。故答案为7。

3.按位异或（^）

用法：a^b(其中a,b为两个整型类型的数值，如果a和b相同则为0，不相同为1）
例如：3^5 怎么来理解呢？
第一步：把3和5转化为各自的二进制表示。3为11，5为101。
第二步：将位数少的补齐多余位。3为11只有两位二进制数，5为101是三位
	   二进制数。我们将11补齐三位为011。
第三步：将其一一对应。
	   3：011
	   5：101
     结果：110
     110的十进制表示为6。故答案为6。

异或常用的性质：
1.交换律：a ^ b = b ^ a
2.结合律：(a ^ b) ^ c = a ^ (b ^ c)
异或在算法竞赛中的小技巧
1.任何数异或0都得任何数不变。
2.任何数异或本身都为0。

4.按位取反（~）

用法：~a(其中a为一个整型类型的数值，如果a为0则取反之后为1，若a为1则取反之后为0）
例如：~5 怎么来理解呢？
第一步：把5转化为二进制表示。5为101。
第二步：将其每一位取反。
	    5：101
     结果：010
     010的十进制表示为2。故答案为2。

5.按位左移（<<）

用法：a << x(将a的二进制表示 左移x位）
例如：5 << 2 怎么来理解呢？
第一步：把5转化为对应的二进制表示。5为101。
第二步：将其二进制表示整体左移两位，低位补0。
	   5：101
     结果：10100
     10100的十进制表示为20。故答案为20。
     OMG我们惊奇的发现：左移两位之后，5变成了20。扩大了4倍。
     从中我们总结出来：左移1位就是将原数乘2。左移n位就是将原数
     扩大2的n次方倍。

6.按位右移（>>）

用法：a >> x(将a的二进制表示 右移x位）
例如：5 >> 2 怎么来理解呢？
第一步：把5转化为对应的二进制表示。5为101。
第二步：将其二进制表示整体右移两位，高位补0。
	   5：101
     结果：001
     001的十进制表示为1。故答案为1。
     OMG我们惊奇的发现：右移两位之后，5变成了1。
     从中我们总结出来：右移1位就是将原数除以2。左移n位就是将原数
     缩小2的n次方倍。

重点：在C++中整数的除法是向0取整。比如5/2=2，-3/2=-1
但是右移的除法是向下取整。比如5/2=2，但是-3/2=-1.5但是由于向下取整答案为-2。

三.位运算中的常见操作

1.求二进制中1的个数

#include<iostreama>
using namespace std;
int n;
int main()
{
	cin >> n;//输入一个数n
	int sum = 0;//记录一下n的二进制表示有多少个1
	while(n)//只要n不等于0就一直执行操作
	{
		if(n & 1) sum++;//将n的最后一位和1相&如果为1说明最后一位是1
		n >> 1;//每判断完一位之后都舍弃最后一位。
	}
	cout << sum;
	return 0;
}