位运算包括 求与&、求或|、异或^、求反~

位运算的妙用

• 判断奇偶数：与1进行求与

• 异或可以理解为不进位的加法：1 + 1 = 0， 0 + 0 = 0， 1 + 0 = 1

• （>>）右移，（<<）左移

• (>>>) 逻辑右移 ，没有(<<<)

• 对于int，1<<35与1<<3是相同的。

例题 1

可以通过异或运算解决。

比如a^ba = b，也就是说两个相同的元素异或为0

所以，(1²3^k....k^1000) ⁽¹2³...^1000) = k，这样就找到了出现两次的元素。

#include <bits/stdc++.h>
using namespace std;
int main()
{
 int a[1001];
 for(int i=0;i<1000;i++)
 a[i] = i+1;
 a[1000] = rand()%1000 + 1;
 int index = rand()%1001;
 int temp = a[index];
 a[index] = a[1000];
 a[1000] = temp;
 for(int i=0; i<1001; i++)
 cout<<a[i]<<" ";
 cout<<endl;
 int x1=0;
 for(int i=1;i<1001;i++)
 x1 = x1^i;
 for(int i=0; i<1001; i++)
 x1 = x1^a[i];
 cout<<x1<<endl;
​
}

例题 2

共有三种解法：

1. 将1左移32次（int类型有32位），与n的每一位求与，求与结果是1表明此位是1，否则此位是0.

2. 将n右移32次（逻辑右移，高位补0），与1求与。

3. 利用(n-1)&n的特性：相当于把n低位上的1去掉，每进行一次就消除了一个1.

#include <bits/stdc++.h>
using namespace std;
int main()
{
 unsigned int n;
 cin>>n;
 cout<<bitset<sizeof(n)*4>(n)<<endl;
​
 int count = 0;
​
 // 将1左移32次，与n的每一位求与比较
 for(int i=0; i<32; i++)
 {
 if((n&(1<<i)) == (1<<i))
 count++;
 }
 cout<<count<<endl;
 count = 0;
​
 //将n逻辑右移32次，与1求与比较
 for(int i=0; i<32; i++)
 {
 if(((n>>i)&1)==1)
 count++;
 }
 cout<<count<<endl;
​
 count = 0;
 //(n-1)&n的效果相当于把n的最低位的1去掉
 while(n != 0)
 {
 n  = ((n-1)&n);
 count++;
 }
 cout<<count<<endl;
 return 0;
​
}

例题3

将整数的奇偶位（二进制）互换

解法：分别构造奇数位为0，偶数位为1和奇数位为1，偶数位为0的两个二进制串。

分别与整数求与，这样就分别提取除了整数二进制的偶数为与奇数位。

将偶数二进制从串右移，奇数二进制串左移，然后求或或者是求异或，即可得到奇偶位互换的结果。

#include <bits/stdc++.h>
using namespace std;
unsigned int m(unsigned int n)
{
 unsigned ji,ou;
 ou = n&0xaaaaaaaa;    //1010 1010 1010 1010
 ji = n&0x55555555;    //0101 0101 0101 0101
 return (ou>>1)|(ji<<1);
}
int main()
{
 unsigned int n;
 cin>>n;
 cout<<m(n)<<endl;
 return 0;
​
}

例题4

#include <bits/stdc++.h>
using namespace std;
int main()
{
 double num;
 cin>>num;
 string s="0.";
 while(num != 0.0)
 {
 //乘2 挪整
 num *= 2;
 //判断整数部分
 if(num >= 1)
 {
 s.append("1");
 //消除整数
 num -= 1.0;
 }
 else
 s.append("0");
​
 if(s.size()>34)
 {
 cout<<"ERROR"<<endl;
 break;
 }
 }
 if(s.size()<=34)
 cout<<s<<endl;
 return 0;
}

例题5

解题思路：k进制的数不进位加法加k次得到的结果是0. 将数组中的所有数转换成k进制表示，然后累加起来，将累加得到的数转成10进制，这个数就是只出现1次的数。

例如：10进制的 4进行不进位加法相加10次，结果为0.