算法专题五: 位运算
常见位运算总结
重点 :
1. 位1的个数
算法思路:
这道题就用到了我们总结的那个第七个方法, 干掉最右侧的1, 知道全部为0位置, 记录并返回干掉次数即可.
class Solution {
public:
int hammingWeight(int n) {
int ret = 0;
while(n)
{
n &= (n-1);
ret++;
}
return ret;
}
};法二: 遍历每一位进行按位与操作, 并没有方法一效率高
class Solution {
public:
int hammingWeight(int n) {
int ret = 0;
for(int i = 0; i < 32 ; i++)
{
if((n & 1) == 1) ret++;
n >>= 1;
}
return ret;
}
};2. 比特位计数
算法思路: 本题也就是求出0到n中每一个数的比特位中1的个数, 很容易想到的方法就是,遍历数组, 按照上一题的思路求出i的1比特位即可.
class Solution {
public:
vector<int> countBits(int n) {
vector<int> ans;
for(int i = 0 ; i <= n; i++)
{
int tmp = i, ret = 0;
while(tmp)
{
tmp &= (tmp - 1);
ret++;
}
ans.push_back(ret);
}
return ans;
}
};3. 汉明距离
算法思路:
也就是求出两个数的比特位不同的个数, 首先对两正数进行异或运算, 不同为1, 然后求出tmp中1的个数, 沿用之前的方法, 先找出最右侧的1, 然后干掉最右侧的1, 记录次数即可.
class Solution {
public:
int hammingDistance(int x, int y) {
int ret = 0;
int tmp = x ^ y;
while(tmp)
{
tmp &= (tmp-1);
ret++;
}
return ret;
}
};4. 只出现一次的数字
算法思路: 仅需将所有数字进行异或, 相同的就被消去了, 最后的数字即为结果.
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ret = 0;
for(int i = 0; i < nums.size(); i++)
{
ret = ret ^ nums[i];
}
return ret;
}
};5. 只出现一次的数字Ⅲ
算法思路: 首先将数组进行异或处理, 结果就是最后两个不同的数字异或的结果, 因为这两个数字不相同, 所以一定有比特位异或的结果为1, 我们仅需据此进行划分为两组即可, 这里我们默认查找最右侧的1, 然后据此进行划分, 分别进行异或, 最后返回分别异或的结果.
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
int ret = 0, tmp = 0;
for(auto& e : nums)
tmp ^= e;
int pos = -1;
for(int i = 0; i < 32; i++)
{
if((tmp & 1) == 1)
{
pos = i;
break;
}
tmp = tmp >> 1;
}
int x1 = 0,x2 = 0;
for(auto& e : nums)
{
if(((e >> pos) & 1) == 1)
x1 ^= e;
else x2 ^e;
}
return {x1,x2};
}
};6. 判定字符是否唯一
本道题可以采用位图的方法进行优化, 因为数据范围只有小写字母, 我们进行一个int的比特位当成哈希表来用即可, 1和0进行两种状态的标记, 处理之前还可以使用鸽巢原理进行一下优化, 也就是26个字母如果字符串长度超过26那么一定有相同的字符串, 这时候直接返回false即可
class Solution {
public:
bool isUnique(string astr) {
int n = astr.size();
if(n > 26) return false;
int bitmap = 0;
for(auto& x : astr)
{
int l = x - 'a';
if(((bitmap >> l) & 1) == 1)
return false;
bitmap |= 1 << l;
}
return true;
}
};7. 丢失的数字
算法思路: 仅需进行异或操作, 将ret和数组进行异或并且和0到size之间的所有i进行异或即可.
class Solution {
public:
int missingNumber(vector<int>& nums) {
int ret = 0;
for(int i = 0; i <= nums.size(); i++)
ret ^= i;
for(auto x : nums)
ret ^= x;
return ret;
}
};8. 两正数之和
算法思路: 本题要求不能使用+ 和 - 运算符将两个数进行相加, 开始总结位运算的时候, 我们也说过^表示的就是我进位相加, 但是进位怎么办, 两数&的结果即为进位, 但是进位并不是加到本位上的, 应该加到前一位, 所以结果我们要进行左移然后相加, 那么问题又来了, 不让使用+怎么进行相加呢, 其实我们在重复上面的操作, 循环即可, 直到进位为0.
class Solution {
public:
int getSum(int a, int b) {
while(b != 0)
{
int add = a ^ b;
int carry = (a & b) << 1;
a = add;
b = carry;
}
return a;
}
};9. 只出现一次的数字Ⅲ
算法思路: 理解题意即可知, 这些数字的每一个bit为相加的结果要么是三的倍数,也就是ret的这一位是0, 要么被三整除余数为1, 也就是ret的这一位是1
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ret = 0;
for(int i = 0; i < 32; i++)
{
int sum = 0;
for(auto x : nums)
sum += ((x >> i) & 1);
if(sum % 3 == 1)
ret |= (1 << i);
}
return ret;
}
};10. 消失的两个数字
算法思路: 首先先将nums中的每一个数和0到N之间每一个数进行异或, 结果为两个数异或的结果, 然后找出1那个位置, 进行划分即可, 分成两组, 再次进行分别异或, 即可得出结果.
class Solution {
public:
vector<int> missingTwo(vector<int>& nums) {
int tmp = 0;
for(int i = 1; i <= nums.size() + 2; i++)
tmp ^= i;
for(auto x : nums)
tmp ^= x;
int dif = 0;
while(1)
{
if(((tmp >> dif) & 1) == 1)
break;
dif++;
}
int a = 0, b = 0;
for(int i = 0; i <= nums.size()+2; i++)
{
if(((i >> dif) & 1) == 1)
a ^= i;
else b ^= i;
}
for(auto x : nums)
{
if(((x >> dif) & 1)== 1)
a ^= x;
else b ^= x;
}
return {a,b};
}
};完
腾讯云开发者
