算法思想之位运算(二)

欢迎拜访：雾里看山-CSDN博客
本篇主题：算法思想之位运算(二)
发布时间：2025.4.13
隶属专栏：算法

滑动窗口算法介绍

位运算（Bit Manipulation）是算法中的高效技巧，通过直接操作二进制位实现快速计算和优化存储

六大基础位运算符

常用模板总结

例题

判定字符是否唯一

题目链接

面试题 01.01. 判定字符是否唯一

题目描述

实现一个算法，确定一个字符串 s 的所有字符是否全都不同。

示例 1：

输入: s = “leetcode”
输出: false

示例 2：

输入: s = “abc”
输出: true

限制：

• 0 <= len(s) <= 100
• s[i]仅包含小写字母
• 如果你不使用额外的数据结构，会很加分。

算法思路

利⽤位图的思想，每一个比特位代表一个字符，一个 int 类型的变量的 32 位足够表示所有的小写字母。比特位里面如果是 0 ，表示这个字符没有出现过。比特位里面的值是 1 ，表示该字符出现过。
那么我们就可以用一个整数来充当哈希表。

代码实现

class Solution {
public:
    bool isUnique(string astr) {
        if(astr.size() > 26)
            return false;
        int num = 0;
        for(auto c : astr)
        {
            if(num>>(c-'a')&1)
                return false;
            else
                num |= 1<<(c-'a');
        }
        return true;
    }
};

汉明距离

题目链接

461. 汉明距离

题目描述

两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。

给你两个整数 x 和 y，计算并返回它们之间的汉明距离。

示例 1：

输入：x = 1, y = 4
输出：2
解释：
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑
上面的箭头指出了对应二进制位不同的位置。

示例 2：

输入：x = 3, y = 1
输出：1

提示：

• 0 <= x, y <= 231 - 1

算法思路

对两个数进行异或操作，异或后1的个数，即为汉明距离。直接使用模板中消去最低位的1，直到变量为零，用一个变量计算次数即可。

代码实现

class Solution {
public:
    int hammingDistance(int x, int y) {
        int ret = 0, n = x ^ y;
        while(n)
        {
            n&=(n-1);
            ret++;
        }
        return ret;
    }
};

丢失的数字

题目链接

268. 丢失的数字

题目描述

给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

示例 1：

输入：nums = [3,0,1]
输出：2
解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。

示例 2：

输入：nums = [0,1]
输出：2
解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。

示例 3：

输入：nums = [9,6,4,2,3,5,7,0,1]
输出：8
解释：n = 9，因为有 9 个数字，所以所有的数字都在范围 [0,9] 内。8 是丢失的数字，因为它没有出现在 nums 中。

提示：

• n == nums.length
• 1 <= n <= 104
• 0 <= nums[i] <= n
• nums 中的所有数字都 独一无二

进阶：你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题?

算法思路

设数组的大小为 n ，那么缺失之前的数就是 [0, n] ，数组中是在 [0, n] 中缺失一个数形成的序列。
如果我们把数组中的所有数，以及 [0, n] 中的所有数全部异或在一起，那么根据异或运算的消消乐规律，最终的异或结果应该就是缺失的数。

代码实现

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

两整数之和

题目链接

371. 两整数之和

题目描述

给你两个整数 a 和 b ，不使用 运算符 + 和 -，计算并返回两整数之和。

示例 1：

输入：a = 1, b = 2
输出：3

示例 2：

输入：a = 2, b = 3
输出：5
提示：

• -1000 <= a, b <= 1000

算法思路

• 异或 ^ 运算本质是无进位加法；
• 按位与 & 操作能够得到进位；
• 然后一直循环进行，直到进位变成 0 为止。

代码实现

class Solution {
public:
    int getSum(int a, int b) {
        int sum = 0, carry = 0;
        do
        {
            sum = a ^ b;// 无进位相加
            carry = (a&b)<<1;// 进位操作
            a = sum;
            b = carry;
        }while(carry != 0);
        return sum;
    }
};

消失的两个数字

题目链接

面试题 17.19. 消失的两个数字

题目描述

给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？

以任意顺序返回这两个数字均可。

示例 1：

输入：[1]
输出：[2,3]

示例 2：

输入：[2,3]
输出：[1,4]

提示：

• nums.length <= 30000

算法思路

本题就是 268. 丢失的数字 + 260. 只出现⼀次的数字 III 组合起来的题。
先将数组中的数和 [1, n + 2] 区间内的所有数异或在一起，问题就变成了：有两个数出现了一次，其余所有的数出现了两次。进而变成了 260. 只出现⼀次的数字 III 这道题。

代码实现

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int n = nums.size() + 2;
        int sum = 0;
        for(auto num : nums)
            sum ^= num;
        for(int i = 1; i <= n; i++)
            sum ^= i;
        int low = (sum==INT_MIN ? sum : sum&(-sum));// 取出最低位
        int ans1 = 0, ans2 = 0;
        for(auto num : nums)
        {
            if(num & low)
                ans1^=num;
            else
                ans2^=num;
        }
        for(int i = 1; i <= n; i++)
        {
            if(i & low)
                ans1^=i;
            else    
                ans2^=i;
        }
        return {ans1, ans2};
    }
};

⚠️ 写在最后：以上内容是我在学习以后得一些总结和概括，如有错误或者需要补充的地方欢迎各位大佬评论或者私信我交流！！！