位运算总结及题目应用(包括求子集）

男娘i 2022-05-30 01:09 155阅读 0赞

位运算既参与运算的两个数据按照二进制位进行相应的运算，位运算在某些功能实现上体现出极大的便利性，比如求子集，寻找数据等等...

**按位与运算符（&）**

运算规则 : 0&0=0 ；0&1=0 ； 1&0=0 ； 1&1=1；

tip： 只有当全为1才是1，其他情况都为0。

负数按补码进行按位与运算！

特性应用 ： 1）数据清零： data&0=0；

**按位或运算（|）**

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

tip: 只要有一个“1”，结果就为1。

负数按补码进行按位或运算！

**按位异或运算（^）**

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

tip : 体现出“异”，对应位不同就为1，同则为0。

特性应用： 1）按位取反： 1^1=0 ,1^0=1 不难发现如果一个二进制数 110^111=001，与一个每一位都是1的二进制数异或，得到的是这个二进制数的取反结果。

2)遇零自保： a^0=a；

3)满足交换律，结合律（a^b^a=b^(a^a)）;

4)对任何的数，都有a^a=0;

5)自反性：b^a^a=b^0=b;

应用：我们都知道要交换两个数，需要应用一个中间变量，但有了异或，可节省一个变量。

例：交换Num1,Num2;

a=a^b;   
        b=a^b;    //相当于 a^(b^b) = a^0 = a; 
        a=a^b;   // 相当于b^(a^a) = b^0 = a;

**右移运算符（>>）**

运算规则：某数各二进制位向右移动若干位，不足位补零。如 2（0010）>>1 （右移1位）=（缺位补零）0001.

特性：每右移一位，相当于除二。

特殊用法：可做打印的打表，例如0111，和1进行与运算，可知某二进制最右位是1还是0，是1则打印数据，每次打印完都data>>1，再和1与运算，重复直到该数为零，不断读取下一位情况。

**左移运算符（<<）**

运算规则：某数各二进制位向左移动若干位，不足位补零。如 2（0010）<<1 （左移1位）=0100（缺位补零）。

特性：每左移一位，相当于乘二。

**应用1：OpenJudge two problem introduce**

题目1链接：[点击打开链接][Link 1]

代码如下

/*finished by SZU-Crayon 2018/2/27*/ 
    /*题目：写出函数中缺失的部分，使得函数返回值为一个整数,该整数的第i位和m的第i位相同，其他位和n相同。*/ 
    #include <iostream>
    using namespace std;
    int bitManipulation1(int n, int m, int i) {
    	//代码补充如下 
    	return (m>>i & 1)>0? 
    			n | ( 1<<i ) :       //第i位是1 和n进行或运算   n原来1还是1 0还是0   "|"和0进行运算不改变原有 
    			n & ~( 1<<i );       //第i位是0 取反和n进行与运算   第i位变成0  0还是0   与1进行与运算n中1还是1 0还是0 
    }
    
    int main() {
    	int n, m, i, t;
    	cin >> t;
    	while (t--) { 
    		cin >> n >> m >> i;
    		cout << bitManipulation1(n, m, i) << endl;
    	}
    	return 0;
    }

题目二链接：[点击打开链接][Link 2]

代码如下：

/*finished by SZU-Crayon 2018/2/27*/
    /*题目：写出函数中缺失的部分，使得函数返回值为一个整数,该整数的第i位是n的第i位取反，其余位和n相同*/
    #include <iostream>
    using namespace std;
    int bitManipulation2(int n, int i) {
    	//代码补充如下 
    	return (n>>i & 1)>0 ?
    		n & ~( 1<<i ) :
    		 n | ( 1<<i ) ;
    }
    
    int main() {
    	int t, n, i;
    	cin >> t;
    	while (t--) {
    		cin >> n >> i;
    		cout << bitManipulation2(n, i) << endl;
    	}
    	return 0;
    }

**应用二:求出不成对存在的两个数**

有一个问题：含有1001个元素的数组，其中1000个元素是从1到1000的数，求出第1001个元素，不难想我们可以把这1001元素进行异或运算，再与1-1000的数异或，借用相同数异或结果为0，0与任意数异或结果还是原来的数，可以把1-1000抵消变成0，0与第1001个数异或结果为第1001个元素。

有一道方法相似的题目如下（代码中附有题目）

/*finished by SZU-Crayon 2018/2/27*/ 
    /*Description
    “第一次有了喜欢的人，还得到了一生的挚友，两份喜悦互相重叠，这双重的喜悦又带来了更多更多的喜悦，本应已经得到了梦幻一般的幸福时光，然而，为什么，会变成这样呢？”双重的喜悦感却无法带来更多的幸福，现在，雪菜在很多喜悦感之中只想要得到两份不重叠的喜悦感（其他的喜悦感都是重叠的），你能帮她找出这两份不同的喜悦感是多少吗？
    Input
    第一行一个整数T，代表数据的组数（1<=T<=10）,接下来T组数据，每组数据的第一行是一个整数n（1<=n<=1000000），第二行是n个整数ai（0 <= ai <= 1000000000）代表喜悦感，每两个整数之间有一个空格，题目保证有且仅有两个不同的整数出现一次，其他的整数都是出现两次。
    Output
    对于每组数据，输出两个整数，分别代表两份不同的喜悦感，中间有一个空格，并且喜悦感较小的先输出。
    Sample Input
    2
    6
    2 2 1 1 3 4
    4
    1 1 3 4
    Sample Output
    3 4
    3 4*/
    #include<bits/stdc++.h>
    using namespace std;
    void TransMax(int& a,int& b)    //传递引用，可改变参数 
    {
    	if(a>b)   //异或交换法，可减少一个中间变量的定义 
    	{
    		a=a^b;   
    		b=a^b;    //相当于 a^(b^b) = a^0 = a; 
    		a=a^b;   // 相当于b^(a^a) = b^0 = a
    	}
    }
    int main()
    {
    	int t,n; int *Num;
    	//int Num[100];
    	cin>>t;
    	while(t--)
    	{
    		int OrRes=0,FindPow=1,Num1=0,Num2=0;
    		cin>>n;
    		Num=new int [n];
    		for(int i=0;i<n;i++)
    		{
    			cin>>Num[i]; 
    			OrRes^=Num[i];     //元素异或处理，因为相同元素异或结果为零，所以所得为两个不成对的元素的异或结果 OrRes = num1^num2 （num1，num2仍未知） 
    		}
    		while( !(FindPow & OrRes) )    //因为两个数不同，故OrRes二进制表示至少有一位是1    通过与运算FindPow & OrRes非零找出靠右的1位 
    			FindPow<<=1;     //FindPow & OrRes = 0表示 FindPow和OrRes没有同个位置的1 ，则FindPow1位左移继续寻找 
    		for(int i=0;i<n;i++)	
    			if(FindPow&Num[i])    //各个元素要么存在一个1位置与FindPow相同要么没有，进行分类；可以将num1，num2分开； 
    				Num1^=Num[i];    
    			else						//每一类分别进行异或运算，因为相同元素肯定在同一类，异或结构分别是两个不成对元素 
    				Num2^=Num[i];
    		delete []Num;
    		TransMax(Num1,Num2);  //比较交换函数，如果Num1>Num2,交换Num1，Num2； 
    		cout<<Num1<<" "<<Num2<<endl;		
    	}
    	return 0;
    }

**应用三：求子集（位运算）**

代码如下：

/*finished by SZU-Crayon 2018/2/27*/ 
    	for(int i=0;i<EleCount;i++)          //n个元素，EleCount = pow（2，n）; 
    	{
    		int Tempi=i;     //由于后面需要对i进行位运算，为防止i数值改变 
    		cout<<"[ ";
    		for( int j=0; j<Length,Tempi; j++,Tempi>>=1 )    //Tempi=0表示该子集元素输出完毕，Tempi>>=1 二进制位全部向右一位，不足位补0 
    			if( Tempi&1 )                     //与运算，如果Tempi最右一位为1，打印该元素，否则位右移继续判定是否打印 
    				cout<<ArrayNum[j]<<" ";
    		cout<<"]"<<endl;
    	}

[Link 1]: http://cxsjsx.openjudge.cn/hw2017total01/A01/
[Link 2]: http://cxsjsx.openjudge.cn/hw2017total01/A02/