位运算的基本操作与应用
位运算介绍
现代计算机中，几乎都是二进制计算机，所有的数据都以二进制的形式存储在设备中。位运算就是直接对存储在内存中的数据的二进制位进行操作。在计算机中，每一个二进制位称为1个bit，单位简写做1b。通常8个bit为一个单位，称为字节(byte)，单位简写作1B。
在C++中表示二进制数一般使用0x前缀表示的十六进制形式，和二进制数有一一对应的关系，如0x5A，表示二进制数 01011010 。
在 n 位二进制数中，我们一般称最低位为第 0位，最高位为 n − 1 位，总右到左依次是第 0 , 1 , 2 , ⋯ , n − 1 位 ，如下图所示：
（我们在计算时，一般使用的是 32位的int 类型(在个人计算机中，int一般为32位)，但为了便于将算法以图形表示，下面一般使用8位的二进制数来展示，而不是使用32位，否则位数太多，图形过小，不利于绘制和阅读。）
假设如果 A = 60，且 B = 13，现在以⼆进制格式表⽰，它们如下所⽰：
A = 0011 1100
B = 0000 1101
则
A&B = 0000 1100(与，对应位两个均为1则得1，否则为0)
A|B = 0011 1101(或，对应位只要有一个为1则得1)
A^B = 0011 0001(异或，对应位相同为0，不同为1)
~A = 1100 0011（非，取反，即0变1，1变0）
<< ⼆进制左移运算符。左操作数的值向左移动右操作数指定的位数。 A << 2 将得到 240，即为 1111 0000，每左移一位，相当于乘2。
⼆进制右移运算符。左操作数的值向右移动右操作数指定的位数。 A >> 2 将得到 15，即为 0000 1111，每右移一位，相当于除2。
注意以下⼏点：
1． 在这6种操作符，只有~取反是单⽬操作符，其它5种都是双⽬操作符。
2． 位操作只能⽤于整形数据，对float和double类型进⾏位操作会被编译器报错。
3． 对于移位操作，右移时⾼位是补符号位。如下⾯代码会输出-4和3。
因为15=0000 1111(⼆进制)，右移⼆位，最⾼位由符号位填充将得到0000 0011即3。-15 = 1111 0001(⼆进制，补码形式)，右移⼆位，
最⾼位由符号位填充将得到1111 1100即-4（见注1）。
int a = -15, b = 15;
printf("%d %d\n", a >> 2, b >> 2);
4． 位操作符的运算优先级⽐较低，尽量使⽤括号来确保运算顺序，否则很可能会得到莫明其妙的结果。⽐如要得到像
1，3，5，9这些2^i+1的数字。写成int a = 1 << i + 1;是不对的，程序会先执⾏i + 1，再执⾏左移操作。应该写成int a = (1<< i) + 1;
又例如 if (a&b!=0) ，会先判断(b!=0)。
5． 另外位操作还有⼀些复合操作符，如&=、|=、 ^=、<<=、>>=。
位运算的应用
- 判断偶数，判断最低位是0还是1即可，⽐求模快
x % 2 != 0 //x正负都可以判断；不⽤x%2 == 1，因为如果x为负奇数，x%2=-1
(x & 0x1) == 0
例如：
int x;
int main()
{
cin>>x;
if((x & 0x1)==0) cout<<"yes";
else cout<<"no";
return 0;
}
2.两个数的交换
a = a^b;//a变为⼀个相同为0，相异为1的结果
b = a^b;//该结果和b做运算，得到原来的a
a = a^b;//该结果和a做运算，得到原来的b
再来个实例说明下以加深印象。int a = 13, b = 6;
a的⼆进制为1101(⼆进制)
b的⼆进制为 110(⼆进制)
第⼀步 a^=b a = 1101 ^ 110 = 1011;
第⼆步 b^=a b = 110 ^ 1011 = 1101;即b=13
第三步 a^=b a = 1011 ^ 1101 = 110;即a=5
3.lowbit运算
lowbit 运算 是位运算中比较重要的运算方式，用于计算一个二进制数最低位的1。
lowbit 即二进制数最低位1所对应的值。
如，二进制数 0b01011000最低的 1是在第3位，对应值为0b1000，即8。
lowbit运算的实现
一个数的lowbit值，即一个数的最低位，可通过如下操作取出，复杂度为 O(1)：
假设原来的数是a，对a取反加1得到~a+1，原数a和~a+1进行位与操作，就得到了lowbit值，即lowbit(a) = a & (~a + 1)。
当这个数是0，没有最低位1的时候，结果为0。
因为取反加1就是一个数的相反数的补码，因为lowbit也写作
lowbit(a)=a&(-a)
一个数消去它的lowbit位，由上面的lowbit求法，直接减去它的lowbit值即可。
即 a-(a&-a)
也可以由a&(a-1)得到
4.求整数的⼆进制表⽰中1的个数，不⽤⼀个⼀个的移位判断
include <bits/stdc++.h>
using namespace std;
int x,cnt;
int main()
{
cin>>x;
while(x!=0)
{
cnt++;
x&=x-1;//将最右边的1置为0；正负都可计算，负数是按照补码计算的，最后的符号位也被统计
}
cout<<cnt;
return 0;
}
5.判断一个数是否2的N次⽅次
题⽬要求：⽤⼀个表达式，判断⼀个数X是否是2的N次⽅，即2,4,8,16……等，要求不可以⽤循环语句。
解析：2,4,8,16这样的数转化成⼆进制是10,100,1000,10000。
如果X减去1后（低⼀位并且⼆进制的每⼀位都是1），这个数与X做与运算，答案若是0，则X是2的N次⽅。
所以答案是：!(x&(x-1))
即可写成：if !(x&(x-1)) cout<<"yes"