位运算基础
说到与(&)、或(|)、非(~)、异或(^)、位移等位运算，就得说到位运算的各种奇淫巧技，下面分运算符说明。
1. 与(&)
计算式 a&b，a、b各位中同为 1 才为 1，否则为0，a&1和a%2效果一样；来看两道典型的题目，第1道计算整数二进制中 1 的位数：
//191. Number of 1 Bits
int hammingWeight(uint32_t n) {
int res=;
while(n!=){
n=n&(n-);
++res;
}
return res;
}
n=n&(n-1)代表去掉整数n二进制中最左侧为 1 的位，例如n=12，则：
n ->
&
n- -> 1 0
------------------
1 0
第2道判断一个数是否为4的乘方数（不能用loop解）：
//342. Power of Four
bool isPowerOfFour(int num) {
if(num==INT_MIN) return false;
return !(num&(num-)) && (num&0x55555555);
}
以上0x55555555的二进制表示为……01010101 (偶数位为0、奇数位为1)，像这样tricky的数还有：
0xaaaaaaaa : (偶数位为1，奇数位为0）
0x33333333 : 00 (1和0每隔两位交替出现)
0xcccccccc : (0和1每隔两位交替出现)
0x0f0f0f0f : (1和0每隔四位交替出现)
0xf0f0f0f0 : (0和1每隔四位交替出现)
相关LeetCode题：
201. Bitwise AND of Numbers Range 题解
2. 或(|)
计算式a|b，a、b各位中有一个为1则结果为1；来看一道题：有正整数n，求小于或等于n的2的最大乘方数（不能用loop解）：
int largest_power(ing N) {
N = N | (N>>);
N = N | (N>>);
N = N | (N>>);
N = N | (N>>);
N = N | (N>>);
return (N+)>>;
}
看起来是不是相当tricky，其思路是用或运算将右边位数置为1，例如n=01010，通过或操作n变为01111，则n+1为10000，所求为01000；更详细解释见 这里
相关LeetCode题：
3. 异或(^)
计算式a^b，a、b对应位相同为0，相异则为1；根据异或性质有a^a=0，a^0=a，利用该性质可解决136. Single Number：
//136. Single Number
int singleNumber(vector<int>& nums) {
int res=;
for(auto x:nums) res^=x;
return res;
}
相关LeetCode题：
4. 位移
a<<1效果相当于a*2(不超出数值类型范围情况下)，a>>1效果相当于a/2，位移常用于按位轮询。
相关LeetCode题：
有意思的时当我们的目光放到bit的维度，一些问题可以按位来求解，例如169. Majority Element求数组中出现次数大于一半的数：
//169. Majority Element
int majorityElement(vector<int>& nums) {
int mask=,size=nums.size(),ret=;
for(int i=;i<32;i++){
int count=;
for(int j=;j<size;j++){
if(nums[j]&mask) count++;
if(count>size/){
ret|=mask; //逐位计算结果break;
}
}
mask<<=;
}
return ret;
}
相关LeetCode题：
421. Maximum XOR of Two Numbers in an Array 题解
使用bit表示数据
在一些场景下我们希望用bit来表示数据，或节省空间或利用bit的运算特性来表示状态转换。
相关LeetCode题：