位运算可以实现哪些功能

ゝ一世哀愁。 2022-08-06 15:03 122阅读 0赞

**位运算可以实现哪些功能**

许多时候，我们为了减少算法的时间复杂度，都是推荐使用位运算，今天我们整理一下位运算可以实现哪些功能。

# 1. 乘除2 #

左移1位乘以2，左移n位乘以2^n；

右移1位除以2，右移n位除以2^n；

举个例子：

#include<iostream>
    using namespace std; 
    
    int main()
    {
    	int a = 16; 
    	int b = 25; 
    
    	//乘除2
    	cout<<(b<<1)<<' '<<(a>>1)<<endl; 
    
    	return 0; 
    }

# 2. 判断奇偶数 #

用到位运算中的按位与，和1按位与。

如下：

#include<iostream>
    using namespace std; 
    
    int main()
    {
    	int a = 16; 
    	int b = 25; 
    
    	// 判断奇偶数
    	if(a & 1)
    		cout<<"Odd"<<endl; 
    	else
    		cout<<"Even"<<endl; 
    
    	return 0; 
    }

# 3. 取余运算 #

还是使用按位与运算符，只不过不再是和1按位与了。

#include<iostream>
    using namespace std; 
    
    int main()
    {
    	int a = 16; 
    	int b = 25; 
    
    	// 取余
    	cout<<(a & 3)<<endl;  // 除以4的余数
    	cout<<(a & 7)<<endl;  // 除以8的余数
    	cout<<(a & 8)<<endl;  // 无效，只能运算2的次幂的余数
    
    	return 0; 
    }

分析：注意这个方法只能计算2的次幂的余数，而且参加按位与的只能是2^n-1，因为这些数的二进制形式全是1.

# 4. 求相反数 #

使用按位取反运算符。

//求相反数
    	cout<<(~a+1)<<endl;

# 5. 求绝对值 #

使用异或运算符（^）

#include<iostream>
    using namespace std; 
    
    int main()
    {
    	int a = -36; 
    	int b = 25; 
    
    	// 绝对值
    	int tmp = a>>31;  // /a大于等于0时tmp为0，a小于0时tmp为-1  
    	int A = (a^tmp)-tmp; 
    	cout<<A<<endl; 
    
    	return 0; 
    }

这些基本的数学运算都是可以通过为运算符来实现，时间复杂度都比较低，以后常用。