位运算符的妙用
一、定义
位运算符用于对整数的二进制位进行操作。
二、常见的位运算符及其说明
1.按位与（&）双目运算符
（1）规则：两个操作数的对应二进制数都为1时，结果位为1，否则为0。
（2）应用
某些位清零/保留某些位：
例a&255可以保留a的低八位，高八位清零。
判断奇偶性：
检查最低位是否为0。
2.按位或（|）
（1）规则：两个操作数的对应二进制数都为0时，结果位为0，否则为1。
（2）应用
某些位置1：
例a|0xFF00可以将高八位设置为1。
3.按位异或（^）
（1）规则：两个操作数的对应二进制数相同时，结果位为0，否则为1。
（2）应用
判断两个数是否相等：a==b等价于！（a^b）=1；
清零操作：x^=x；
交换：
n个元素1~n之间，元素无重复，丢（多）了一个，如何找到丢（多）的元素？
1^2^……^n^（丢（多）了一个元素的n-1（n+1）个元素）结果就是丢的元素。
4.取反（~）
（1）规则：对操作数的每一个二进制位取反，1变为0，0变为1。
（2）应用
求负数：
正数的取反结果为其负数的补码。
5.左移（<<）
（1）规则：将操作数的二进制位向左移动指定位数，高位丢弃，低位补0。
（2）应用
左移n位相当于乘以2的n次方。
6.右移（>>）
（1）规则：将操作数的二进制位向右移动指定位数，高位补符号位，低位丢弃。
（2）应用
右移n位相当于除以2的n次方。
三、练习
1.找到两个只出现一次的元素
n个元素其中有两个元素仅出现一次，其他元素都出现偶数次，找到两个只出现一次的元素。
#include<vector>
#include<iostream>using namespace std;void seekOnlyOne(vector<int>& arr) {int len = arr.size();int res = 0;//1.将这len个数字进行异或运算for (int i = 0; i < len; ++i){res = res ^ arr[i];}//2.判断res哪位为1,第mark位第一个为1int mark = 1;while (1){//2.1如果末位为1，退出循环if (res & 1) { break; }//2.1如果末尾为0，右移，标志位加1res = res >> 1;mark++;}int res1 = 0, res2 = 0;//3.遍历数组mark位为1和mark位为0的分别异或for (int i = 0; i < len; ++i) {//3.1mark位为1if (arr[i] & (1<<(mark-1))) {res1 = res1 ^ arr[i];}else {res2 = res2 ^ arr[i];}}printf("这两个数分别为%d,%d", res1, res2);
}int main()
{vector<int>arr = { 8,6,3,2,9,5,9,8,2,3 };seekOnlyOne(arr);return 0;
}2.两个整数不用+-*/实现四则运算
不用+实现加法运算
/*不用"+"实现加法运算*/
//(一)
int jiaFa(int a,int b)
{while (1) {//1.获得不需要进位的位int x = (a ^ b);//2.获得需要进位的位int y = (a & b);//3.检查有无进位，无：结束，有：继续if (y!=0) {//4.1有：继续，进位y = y << 1;//4.更新计算对象a = x;b = y;}else {//4.2无：结束return x;}}
}
//优化：
//（二）可使用递归代替循环
int jiaFa2(int a, int b)
{//1.获得不需要进位的位int x = (a ^ b);//2.获得需要进位的位int y = (a & b);//3.检查有无进位，无：结束，有：继续if (y == 0) { return x; }y = y << 1;return jiaFa2(x, y);
}
//（三）简便
int jiaFa3(int a, int b)
{while (1) {//1.获得不需要进位的位int x= (a ^ b);//2.获得需要进位的位int y= ((a & b)<<1);a = x; b = y;//3.检查有无进位，无：结束，有：继续if (b == 0) {return a;}}
}
//（四）do while
int jiaFa4(int a, int b)
{do{//1.获得不需要进位的位int x = (a ^ b);//2.获得需要进位的位int y = ((a & b) << 1);a = x; b = y;} while (b != 0);//3.检查有无进位，无：结束，有：继续return a;
}不用-实现减法运算
/*不用"-"实现减法运算*/
int jianFa(int a, int b)
{b = -b;return jiaFa(a, b);
}不用*实现乘法运算
/*不用"*"实现乘法运算*/
int chengFa(int a, int b)
{int res = 0; //用来存储部分积//若乘数为0结束循环while (b != 0) {//1.判断乘数末尾是否为0if (b % 2 != 0){//2.1 若为1,更新部分积，被乘数左移一位，乘数右移一位res += a;a = a << 1;b = b >> 1;}else {//2.2 若为0，被乘数左移一位，乘数右移一位a = a << 1;b = b >> 1;}}return res;
}