位运算理解

在涉及数字的算法中，如果要追求最优解，往往会使用位运算，而位运算在高中以前接触不多，印象不够深刻，所以特此系统的学习位运算，并运用在一些很作者认为很奇妙的算法中。

位运算基础

	&	^	$\vert$	~	>>	<<
名称	与	异或	或	非	右移	左移
0 1	0	1	1
1 0	0	1	1
1 1	1	0	1
0 0	0	0	0

所有的位运算都先将数字转化为二进制（从左到右对应高位到低位），再进行对应的操作

位运算性质

（也不能说是所有的性质，只是算法中会用的一些方法）

1. a^a=0
2. a^0=a
3. a>>1相当于a/2，a<<1相当于a*2
4. a&(a-1)是移除最末尾的1（与最低位的1不同）
5. 偶数&1==0，奇数&1==1(奇偶判断的新方式)

算法应用

加法

有点加法器运算的感觉

int sum (int a, int b) 
{
    return b ? sum (a^b, (a&b) << 1) : a;
}

找单出来的数字

要求：在一个int数组中，除了一个数字只出现一次，其余数字均出现两次，找出出现一次的数字（原题目忘记了，但意思是这样）

分析：利用异或的性质a^a=0，使用位运算对数组内所有数字取异或和，所有出现两次的数字异或和将为0，最终只留下出现一次的数字

int singleNumber(vector<int>& nums) {
    int tmp = 0; 
    for(int i = 0;i < nums.size();i++){   
        tmp = tmp ^ nums[i];
    }
    return tmp;
}

找缺掉的两个数字

要求：给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。在 O(N) 时间内只用 O(1) 的空间找到它们，以任意顺序返回这两个数字均可

分析：

计算不大于a且能被4整除的最大数

要求：给定一个数字max_num，求不大于max_num的最大数，且该数字是4的倍数

int getNum(int max_num){
    return max_num & ~3;
}