算法基础： 位运算

位运算

目录

位运算

概念

常用操作

算法考题

---

概念

就是直接对存储在内存中的数据的二进制位进行操作。在计算机中，每一个二进制位称为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

常用操作

交换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 < 
一个数组中只有一个数出现了N数次，其他数都出现了M数次，怎么找到这个数
 
思路：借助一个32个元素的数组，将所有的数据的二进制（32位数）如果为1.就将数组下标对应位加1，之后判断哪些可以不可以被M整除，且余数为N
 
int function(vector arr,int k,int m)
{
    array bit_arr{0};
    for(int index =0 ;index