算法基础： 位运算
位运算
目录
位运算
概念
常用操作
算法考题
概念
就是直接对存储在内存中的数据的二进制位进行操作。在计算机中，每一个二进制位称为1个bit，单位简写做 b。通常8个bit为一个单位，称为字节(byte)，单位简写作 B。
在C/C++中表示二进制数一般使用用0x前缀表示的十六进制形式，和二进制数有一一对应的关系，如0x5A，表示二进制数 01011010 0101 101001011010。
C++中二进制字面量直到C++14标准才补上，以0b 或 0B表示，如 0b01011010，但C语言标准一直没有，只在GNU C编译器上有相应的扩展语法，所以在代码中以0b为前缀的数有可能编译不过。
- 按位与运算(&)， 同为1，则为1
- 按位或运算(|),有1，则为1.
- 按位异或运算(^)，不同，则为1.
- 求反运算(~),1则为0，0则为1.
- <<n左移n位,右补0。实际含义相当于*2^n
- >>n右移n位，左补0.实际含义相当于/2^n
常用操作
交换swap
异或操作
注意：必须是两块内存，不然会把自己洗成0！
int a = 10; int b = 11; a = a^b; b = a^b; b = a^b;
平均值
(x+y)>>1
取mid
L+(（R-L）>>1)
2的n次方
1 << n
判断符号是否相同
(x^y)>=0
判断奇偶性
(n &1) ==1
32位int取绝对值
(n ^ (n >> 31)) - (n >> 31)
判断n是否是2的整数次幂
n&(n-1) == 0
获取一个数二进制最右面的一个1
x&（（~x）+1）
算法考题
一个数组中只有一个数出现了奇数次，其他数都出现了偶数次，怎么找到这个数，
思路：相同的数被异或变为0，只有那个奇数的会留下来。
int arr[9] = {1,2,3,4,5,1,2,3,4};
int val = 0;
for(int i =0;i<9;i++) {
val = val^arr[i];
}
一个数组中只有两个数出现了奇数次，其他数都出现了偶数次，怎么找到这个数
思路： 如果只有两个数是奇数，那么所有值的异或结果一定包含了这两个值的异或结果，这个值的二进制就代表了剩余的两个奇数项的值的二进制不同，我们从中找到一个1的位数N。
然后就可以再使用一个数去异或N位上为1的数，这个时候就可以找到一个数，再用这个数去异或最开始全量异或算出的value，就可以得到另外一个数。
int arr[9] = {1,2,3,4,5,1,2,3,4,6};
int val1 = 0;
for(int i =0;i<9;i++) {
val1 = val^arr[i];
}
int right_one = val1 & (~val1 +1);
int val2 =0;
for(int i =0;i<9;i++) {
if(arr[i]&right_one == 0) {
val2^=arr[i];
}
}
cout <<val2 <<val2^val1<<endl;
一个数组中只有一个数出现了N数次，其他数都出现了M数次，怎么找到这个数
思路：借助一个32个元素的数组，将所有的数据的二进制（32位数）如果为1.就将数组下标对应位加1，之后判断哪些可以不可以被M整除，且余数为N
int function(vector<int32_t> arr,int k,int m)
{
array<int,32> bit_arr{0};
for(int index =0 ;index <arr.size();index ++) {
for(int i =0;i<32;i++) {
if((arr[index] & (1<<i)) != 0)
{
bit_arr[i] ++;
}
}
}
int32_t num = 0;
int i =0;
for(auto &a : bit_arr) {
if(a%m == 0) {
i++;
continue;
}
if(a%m == k) {
num |= (0x01<<i);
i++;
}
}
return num;
}
int main()
{
cout<<function({1,1,1,2,2,2,3,3},2,3)<<endl;
}