C++ 位运算

任何信息在计算机中都是采用二进制表示的，数据在计算机中是以补码形式存储的，位运算就是直接对整数在内存中的二进制位进行运算。由于位运算直接对内存数据进行操作，不需要转换成十进制，因此处理速度非常快。

一、位运算符

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

1：按位与运算符（&） 

 “a&b”是指将参加运算的两个整数a和b，按二进制位进行“与”运算。

运算规则：0&0=0;  0&1=0;   1&0=0;    1&1=1;      

即：两位同时为“1”，结果才为“1”，否则为0
例如：3&5  即 0000 0011& 0000 0101 = 0000 0001  因此，3&5的值得1。
另，负数按补码形式参加按位与运算。
按位与&比较实用的例子：
1、比如我们经常要用的是否被2整除，一般都写成   if(n % 2 ＝＝ 0) 可以换成 if((n&1) ＝＝ 0) 
2、按位与运算可以取出一个数中指定位。例如：要取出整数84从左边算起的第3、4、5、7、8位，只要执行84 & 59,因为84对应的二进制为01010100，59对应的二进制为00111011，01010100 &  00111011=  00010000   可知84从左边算起的第3、4、5、7、8位分别是0、1、0、0、0。
 3、清零。如果想将一个单元清零，使其全部二进制位为0，只要与一个各位都为零的数值相与，结果为零。

与运算的用途：

1）清零

如果想将一个单元清零，即使其全部二进制位为0，只要与一个各位都为零的数值相与，结果为零。

2）取一个数的指定位

比如取数 X=1010 1110 的低4位，只需要另找一个数Y，令Y的低4位为1，其余位为0，即Y=0000 1111，然后将X与Y进行按位与运算（X&Y=0000 1110）即可得到X的指定位。

3）判断奇偶

只要根据最未位是0还是1来决定，为0就是偶数，为1就是奇数。因此可以用if ((a & 1) == 0)代替if (a % 2 == 0)来判断a是不是偶数。

4）整数幂

判断一个数n ，是不是2的整数幂。比如：64＝2^6,所以输出“yes”,而65无法表示成2的整数幂的形式，所以输出“NO”。 

#include<bits/stdc++.h>
using namespace std;
int main()
{  int n;
   cin>>n;
   if(n&(n-1))cout<<"NO";
   else cout<<"Yes";
}

 2：按位或运算符（|） 

运算规则：0|0=0；  0|1=1；  1|0=1；   1|1=1； 

或运算的用途：

1）常用来对一个数据的某些位设置为1

比如将数 X=1010 1110 的低4位设置为1，只需要另找一个数Y，令Y的低4位为1，其余位为0，即Y=0000 1111，然后将X与Y进行按位或运算（X|Y=1010 1111）即可得到。

3：按位异或运算符（^）

运算规则：0 ^ 0=0；  0 ^ 1=1；  1^ 0=1；   1^1=0； 

异或的几条性质:

• 1、交换律
• 2、结合律 (a^b)^c == a^(b^c)
• 3、对于任何数x，都有 x^x=0，x^0=x
• 4、自反性: a^b^b=a^0=a;

异或运算的用途：

1）翻转指定位

比如将数 X=1010 1110 的低4位进行翻转，只需要另找一个数Y，令Y的低4位为1，其余位为0，即Y=0000 1111，然后将X与Y进行异或运算（X^Y=1010 0001）即可得到。

2）与0相异或值不变

例如：1010 1110 ^ 0000 0000 = 1010 1110

4：按位取反运算符（~）

按位取反运算符（~）是指将整数的各个二进制位都取反，即1变为0，0变为1。 

5：左移运算符（<<）

左移运算符是用来将一个数的各二进制位左移若干位，移动的位数由右操作数指定（右操作数必须是非负值），其右边空出的位用0填补，高位左移溢出则舍弃该高位。

在高位没有1的情况下，左移1位相当于该数乘以2，左移2位相当于该数乘以2*2＝4,15＜＜2=60，即乘了４。
但此结论只适用于该数左移时被溢出舍弃的高位中不包含1的情况。

例如：143<<2  结果为60   因为143转换为进制为10001111，左移2得00111100 ，结果为60。

定义：将一个运算对象的各二进制位全部左移若干位（左边的二进制位丢弃，右边补0）。

设 a=1010 1110，a = a<< 2 将a的二进制位左移2位、右补0，即得a=1011 1000。

若左移时舍弃的高位不包含1，则每左移一位，相当于该数乘以2。

6：右移运算符（>>）

定义：将一个数的各二进制位全部右移若干位，正数左补0，负数左补1，右边丢弃。

例如：a=a>>2 将a的二进制位右移2位，左补0 或者 左补1得看被移数是正还是负。

操作数每右移一位，相当于该数除以2。

7：复合赋值运算符

 位运算符与赋值运算符结合，组成新的复合赋值运算符，它们是：

1、&=   例：a &=b       相当于a=a& b
2、|=   例：a |=b           相当于a=a |b
3、>>=  例：a >>=b    相当于a=a>> b
4、<<= 例：a<<=b      相当于a=a<< b
5、^=   例：a ^= b       相当  a=a ^b