我爱学算法之—— 位运算（中）

努力学习的小廉

1161人浏览 · 2025-09-20 18:39:04

努力学习的小廉 · 2025-09-20 18:39:04 发布

一、判定字符是否唯一

题目解析

在这里插入图片描述

对于这道题，给的一个字符串，要求我们判断该字符串中的所有字符是否完全都不同；

如果存在相同字符，就返回false；否则就返回true

其中字符串s中只存在小写字母。

算法思路

解法一：

使用hash（set/unordered_set）统计字符串s中的每一个字符，当出现相同字符就返回false；

遍历完s，还是没有出现相同字符就返回true。

解法二：

题目中也提到：如果不使用额外的数据结构，会很加分。

这里我们也可以不使用额外的数据结构，当然不是使用数组来统计每个字符。

字符串s中，只存在小写字母（26个小写字母）；并且我们只需判断是否存在相同的字母即可。

所以，这里就可以使用位图来统计每个小写字母是否存在。

遍历字符s，判断字符e是否存在
判断位图bitmap中，二进制第e-'a'位是否为1；
为1则表示该字符已经出现过；不为1则表示该字符之前没有出现过，将要将第e-'a'位修改为1。

代码实现

class Solution {
public:
    bool isUnique(string astr) {
        int bitmap = 0;
        for (auto& e : astr) {
            int i = e - 'a';
            // 判断第i位是否为1
            int tmp = bitmap;
            if (((tmp >> i) & 1) == 1)
                return false;
            else
                bitmap |= (1 << i);
        }
        return true;
    }
};

二、丢失的数字

题目解析

在这里插入图片描述

对于这道题，给定一个包含[0 , n]中n个数的数组nums，要求找出数组nums中，[0 , n]范围内没有出现的数字。

简单来说就是：[0 , n]中一共n+1个数，在数组中nums只存在n个，要找出nums中不存在的那一个数。

算法思路

这道题要直接去找这个不存在的数，使用hash统计还是非常麻烦的；

思路：

数组nums中，一个存在n个数，[0 , n]中的n个数（每个数出现一次）；

而数组下标范围：[0 , n-1]（0到n-1，n个数，每个数出现一次）；

如果再增加一个数n，那在nums中（包含下标），[0 , n]中只有一个数只出现了一次，其他数都出现了两次。

问题就转化为：只出现一次的数字

所以，只需让n按位与上数组下标[0 , n]和数组nums中的每一个数；即可找出这一个丢失的数字。

代码实现

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int ret = n;
        for (int i = 0; i < n; i++) {
            ret ^= i;
            ret ^= nums[i];
        }
        return ret;
    }
};

三、两整数之和

题目解析

在这里插入图片描述

这道题很简单，题如其名：给定两个整数，不使用运算符+/-，计算并返回两整数之和。

算法思路

这道题，如果不讲武德，直接就返回a + b，就太没有意思了。

这里我们可以使用位运算^和&操作来计算a+b：

^按位与操作，也就相等于无进位相加，要使用位运算来计算a+b，也就只用考虑进位问题了

^：无进位相加

进位：只有a和b对应bit位都为1时才会产生进位；（而进位是要加到高位去的(a&b) << 1)

有了无进位相加a^b、进位(a&b) << 1，就要计算a^b+(a&b) << 1，就又要计算无进位相加和进位，并计算和。

直到进位为0，才计算完毕。

在这里插入图片描述

代码实现

class Solution {
public:
    int getSum(int a, int b) {
        int ret = a ^ b;
        int carry = (a & b) << 1;
        while (carry != 0) {
            a = ret;
            b = carry;
            ret = a ^ b;
            carry = (a & b) << 1;
        }
        return ret;
    }
};