位运算介绍

位运算是二进制的一种运算，由于计算机先将10进制数转化成2进制数，而位运算直接进行二进制的运算，所以有时位运算极其方便。下面介绍几种常见的运算符：

1.（ & ）按位与运算符若两个数的二进制数相应位都是1，则该位是1，否则是0.。

2.（ | ）按位或运算符若两个数的二进制数相应位只要有一个是1，则该位是1，否则是0。

3.（ ^ ）异或运算符若两个数的二进制数相应位相同则是0，否则是1。

4.（ ~ ）取反运算符用于求整数的二进制反码，即分别将操作数各二进制位上的1变为0，0变为1。

5.（>>）右移运算符右移运算符是用来将一个数的各二进制位右移若干位，且移动到右端的低位被去掉，高位补0

5.（<<）左移运算符左移运算符是用来将一个数的各二进制位左移若干位，且移动到右端的低位被去掉，高位补0

6.杂论：

（1）求二进制数中1的个数。

比如一个二进制数 01111001010101100，设其相应的10进制数是k，要求其1的个数，只需和00000000000000001按位与，即k&flag,10进制下flag是1，

如果k&flag==1，则该位是1，否则是0。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int f(int n)
 4 {
 5     int ans=0,flag=1;
 6     while(flag)
 7     {
 8         if(n&flag)
 9         {
10             ans++;
11         }
12         flag=flag<<1;
13     }
14     return ans;
15 }
16 int main()
17 {
18     int n;
19     cin>>n;
20     cout<<f(n)<<endl;
21     return 0;
22 }

View Code

（2）判断一个整数是不是2的整数次幂。

如果一个数是2的整数次幂，则该数的二进制数只有一个1，所以只需判断k&(k-1)是否为0，因为满足要求的k的二进制只有一个1，且k-1的二进制恰是k二进制0都变成1，1变成0，

比如64二进制是1000000，63是111111

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int judge(int x)
 4 {
 5     if(x&(x-1)) return false;
 6     return true; 
 7 }
 8 int main()
 9 {
10     int n;
11     cin>>n;
12     if(judge(n)) cout<<"YES"<<endl;
13     else cout<<"NO\n"<<endl;
14     return 0;
15 }

View Code

（3）求m的二进制变成n的二进制需要的次数。

显然用异或解决，让k=m^n,那么k的二进制中为0的表示不需要改变的次数，为1就要改变，所以只需统计k二进制中1的个数

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int f(int m,int n)
 4 {
 5     int k=m^n;int ans=0,flag=1;
 6     while(flag) {
 7         if(k&flag) ans++;
 8         flag=flag<<1;
 9     }
10     return ans;
11 }
12 int main()
13 {
14     int m,n;
15     cin>>m>>n;
16     cout<<f(m,n)<<endl;
17     return 0;
18 }

View Code