【C++刷题】优选算法—

【C++刷题】优选算法——位运算

本文主要是介绍【C++刷题】优选算法——位运算，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

常见位运算操作总结：

基础位运算
&：有0则为0
|：有1则为1
^：相同为0，相异为1 / 无进位相加
运算符的优先级
管它什么优先级，加括号就完事儿了
给一个数 n，确定它的二进制表示中的第 i (默认是从右起第0位) 位是 0 还是 1
(n >> i) & 1
将一个数 n 的二进制表示的第 i 位修改为 1
n |= (1 << i)
将一个数 n 的二进制表示的第 i 位修改成 0
n &= (~(1 << i))
提取一个数 n 二进制表示中最右侧的 1 （lowbit操作）
n & (-n)
(-n) 将 n 最右侧的 1 的左边的区域全部变成了相反的位
干掉一个数 n 二进制表示中最右侧的 1
n &= (n - 1)
(n - 1) 将 n 最右侧的 1 的右边的区域(包括最右侧的1)，全部变成了相反的位
异或 ^ 运算的运算律
n ^ 0 = n
n ^ n = 0 - 消消乐
a ^ b ^ c = a ^ (b ^ c)

根据第6、7条位运算操作，可以搞定1-3题。

位1的个数

int hammingWeight(int n)
{int ret = 0;while(n){++ret;n &= (n - 1);}return ret;
}

比特位计数

int hammingWeight(int n)
{int ret = 0;while(n){++ret;n &= (n - 1);}return ret;
}
vector<int> countBits(int n)
{vector<int> ret(n + 1);for(int i = 1; i <= n; ++i){ret[i] = hammingWeight(i);}return ret;
}

汉明距离

int hammingWeight(int n)
{int ret = 0;while(n){++ret;n &= (n - 1);}return ret;
}
int hammingDistance(int x, int y)
{int ret = 0;while(x && y){if((x & (-x)) < (y & (-y))){++ret;x &= (x - 1);}else if((x & (-x)) > (y & (-y))){++ret;y &= (y - 1);}else{x &= (x - 1);y &= (y - 1);}}ret += hammingWeight(x);ret += hammingWeight(y);return ret;
}

结合第 8 条位运算操作，可以搞定4-5题。
4. 只出现一次的数字

int singleNumber(vector<int>& nums)
{int ret = 0;for(int e : nums) ret ^= e;return ret;
}

只出现一次的数字 III

vector<int> singleNumber(vector<int>& nums)
{long long lowbit = 0;for(int e : nums) lowbit ^= e;lowbit &= (-lowbit);long long low_0 = 0, low_1 = 0;for(int e : nums){if(e & lowbit) low_1 ^= e;else low_0 ^= e;}return {(int)low_0, (int)low_1};
}

判定字符是否唯一

bool isUnique(string astr) 
{if(astr.size() > 26) return false;int hash = 0;for(char c : astr){int bit = 1 << (c - 'a');if( hash & bit ) return false;else hash |= bit;}return true;
}

丢失的数字

// 高斯求和
int missingNumber(vector<int>& nums)
{int n = nums.size();int sum = (0 + n) * (n + 1) / 2;for(int e : nums) sum -= e;return sum;
}// 异或 运算律
int missingNumber(vector<int>& nums)
{int n = nums.size();int ret = 0;for(int i = 0; i <= n; ++i) ret ^= i;for(int e : nums) ret ^= e;return ret;
}

两整数之和

int getSum(int a, int b)
{while(b){int no_carry = a ^ b;int carry = (a & b) << 1;a = no_carry;b = carry;}return a;
}

只出现一次的数字 II

int singleNumber(vector<int>& nums)
{int ret = 0;for(int i = 0; i < 32; ++i){int num = 0;for(int e : nums) if( e & (1 << i) ) ++num;if(num % 3) ret |= (1 << i);}return ret;
}

消失的两个数字

vector<int> missingTwo(vector<int>& nums)
{int n = nums.size();int N = n + 2;int num = 0;for(int i = 1; i <= N; ++i) num ^= i;for(int e : nums) num ^= e;int lowbit = num & (-num);int low_0 = 0, low_1 = 0;for(int i = 1; i <= N; ++i){if(i & lowbit) low_1 ^= i;else low_0 ^= i;}for(int e : nums){if(e & lowbit) low_1 ^= e;else low_0 ^= e;}return {low_0, low_1};
}