1. 常见的位运算技巧
(1) 判断奇偶
奇数最后一位为1，偶数为0
if(num&1){} //奇数
else {} //偶数
(2) 交换两数
if(a!=b) a^=b,b^=a,a^=b;
(3) 变换符号
二进制取反+1就可以将正变负，负变正。
return ~a+1;
（4）取出某一位的数字
int val=(x >> i) & 1
2. 移位取值
这一类题目都运用到了前面提到的取出某一位数字的技巧，这种方法将位运算转化为类似字符串的操作形式，十分简便。
136 只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素
输入: [4,1,2,1,2]
输出: 4
解答：
假设数组是001,001,000,000,011，多余的元素是011，最后一位操作加起来取余2，余下了1，所以，多余元素就是1。
int singleNumber(vector<int>& nums) {
int target = 0;
for (int i = 0; i < 32; i++)
{
int sum = 0;
for (auto x : nums)
//取出单个比特的数字
sum += (x >> i) & 1;
int residue = sum % 2;
target = target | residue << i;
}
return target;
}
137 只出现一次的数字 II
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。
输入: [0,1,0,1,0,1,99]
输出: 99
解答：
方法和上面一样，不过是取余3而已。
int singleNumber(vector<int>& nums) {
int res=0;
for(int i=0;i<32;i++)
{
int sum=0;
for(auto x:nums)
sum+=(x>>i)&1;
int residue=sum%3;
res|=residue<<i;
}
return res;
}
169 多数元素
给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
输入: [2,2,1,1,1,2,2]
输出: 2
解答：
和上面两题一脉相承，如果数组有7个元素，而001是众数，则第0位的1的数量一定大于等于4，0的数量小于等于3，所以只需要比较0和1的数量就可以判断。
int majorityElement(vector<int>& nums) {
int res=0;
for(int i=0;i<32;i++)
{
int zeros=0;
int ones=0;
for(auto x:nums)
{
if((x>>i)&1) ones++;
else zeros++;
}
if(ones>zeros) res|=1<<i;
}
return res;
}
190 颠倒二进制位
颠倒给定的 32 位无符号整数的二进制位。
输入: 00000010100101000001111010011100
输出: 00111001011110000010100101000000
解答：
利用栈的特性。
uint32_t reverseBits(uint32_t n) {
stack<int> st;
uint32_t res=0;
for(int i=0;i<32;i++)
{
int val =(n>>i)&1;
st.push(val);
}
for(int i=0;i<32;i++)
{
res|=st.top()<<i;
st.pop();
}
return res;
}
191 位1的个数
编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）
输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
解答：
极其简单，也可以一行解决return bitset<32>(n).count();
int hammingWeight(uint32_t n) {
int res=0;
for(int i=0;i<32;i++)
{
if((n>>i)&1)
res++;
}
return res;
}