当前位置：首页 > news >正文

深度解析算法之位运算

news 来源：原创 2025/7/30 13:00:39

33.常见位运算

1.基础位运算

<< 左移操作符
> >右移操作符号
~取反
&按位与：有0就是0
|按位或：有1就是1
^按位异或：相同为0，不用的话就是1 /无进位相加

0 1 0
0 1 1
0 1 0 按位与结果
0 1 1 按位或结果
0 0 1 按位异或结果

2.给一个数n，确定他的二进制表示中的第x位是0还是1

n: 0 1 1 0 1 0 1 0 0 1
右边是最低位，下标从0开始，这个下标和右移操作对应的
下标为2的数是0，那么我们想让这个数变成最低位的话，那么我们就得让这个数右移2位，就是下标的大小

现在我们想判断我们第x位是不是1，那么我们让这个位上的数按位与1，但是前提我们先得让这个第x位上的数变成最低的位置，所以我们需要将这个数右移x位，那么我们当时要判断的数就跑到最前面了，然后&1，如果结果是1的话，那么就说明这个位置上的数是1，因为我们的1比较特殊，1的二进制只有最低位是1，其余全是0

如果一个数按位与1之后的话，如果是0 的话，那么这一位数就是0，如果是1的话那么这一位上的数就是1

运算符的优先级能加括号就加括号
所以我们这里的代码就是==（n>>x）&1==

3.将一个数n的二进制表示的第x位修改成1

我们先让这一位上的数按位或上1，那么原本这一位是0的，现在0|1得到的就是1了，但是我们得让其他位的数字不变，其他位的数按位或上一个0就行了，按位或的话就是是1就是1，不是1的话就是0，那么过程就是下面的样子，所以我们原本的二进制数按位或上中间的那串数，但是这个数怎么来呢？
我们直接让1左移x位就行了

所以代码就是 n | =(1<<x)
先让1左移x位，然后n或等上这个数就可以让我们x位变成1了

4.将一个数n的二进制表示的第x位修改成0

我们仅需要将x位变成0，那么我们让这一位按位与上一个0就行了
为了保持其他位置不变，其他位置与上一个1就行了
我们先让这个1左移x位，然后将左移完的结果进行取反操作
所以代码就是:
n&=(~(1<<x))

5.位图

本质就是一个哈希表

6.提取一个数（n）二进制表示中最右侧的1

如果一个数是0 1 1 1 0 1 0 1 0 0 0
如果将最低位提取出来的话就变成了0 0 0 0 0 0 0 1 0 0 0
我们直接使用代码n&-n就行了

如果一个数前面加上-号的话那么就是按位取反再+1
比对原来的数，我们可以发现改变的仅仅是左边的区域，这个最右边的1的右边的区域是没有被改变的，而且左边的区域的数字和之前都是相反的

所以-n的操作就是将最右侧的1左边的区域全部变成相反数
然后将原来的数和变负的数进行按位与的操作，那么除了最右侧的1，其他的都变成0
代码：n&-n

7.干掉一个数（n）二进制表示中最右侧的1

就是将一个数二进制数中最右侧的1变成0
代码就是n&(n-1)

我们的一个数经历了n-1之后，我们最右侧的1前面的数字都是保持不变的，将最右侧的1，右边的区域（包含1）全部变成相反

最后的代码就是n&(n-1)

8.异或（^）运算的运算律

a^o=a

a^a=0

a^ b^ c=a^ (b ^c)

34.判断字符是否唯一

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

示例 1：

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

示例 2：

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

限制：

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

解法一：hash，判断出现的次数，从前往后进行扫描，如果一个数出现的次数大于1的话，那么就说明出现重复的数，那么我们直接返回了false
时间复杂度和空间复杂度都是O(N)

解法二：借助位图的思想

鸽巢原理（抽屉原理）进行优化

class Solution {public:bool isUnique(string astr){//利用鸽巢原理来进行优化if(astr.size()>26) return false;//如果字符串的长度大于26（即超过了字母表中的26个字母），则必定有重复字符。因此可以直接返回false。这是一个基于鸽巢原理的优化：26个字符的字符串最多只能容纳26个不同字符。int bitMap=0;for(auto ch:astr){int i=ch-'a';//定义对应字符的比特位//先判断字符是否已经出现了if(((bitMap>>i)&1)==1) return false;//判断我们位图的第i位是否为1//先让这个位图右移i位到达对应的位置，如果这个数按位与1的结果是1的话，那么就说明这个数已经出现过了，那么我们直接返回fslse就行了//这里的话就说明我们的字符并没有在位图中出现过，那么我们直接将当前字符加入到位图中bitMap |=1<<i;//我们先让1左移i位，因为这个数之前没出现过，所以位置上是0，所以我们直接进行按位或，那么位图上面就会变成1了}//出了循环还没返回的话就说明我们的这个字符串并没有重复的字符return true;}};

如果字符串的长度超过了26的话，肯定存在重复的字符的，所以我们直接return false就行了

35.丢失的数字

题目链接
给定一个包含 [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 中。

我们可以利用一个哈希表进行问题对的解决，但是时间复杂度是O(N)的，空间复杂度一样

我们也可以利用高斯求和进行问题解决，时间复杂度是O(N)的，空间复杂度是O（1）

我们这里使用位运算（异或运算的运算律）
我们将所有的数异或到一起，最终的结果就是我们缺失的数

class Solution {public:int missingNumber(vector<int>& nums){int ret=0;for(auto x:nums) ret^=x;//将这个数组进行累异或操作for(int i=0;i<=nums.size();i++) ret^=i;//将数组中的数 异或到一起return ret;}};

36.两整数之和

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

示例 1：

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

示例 2：

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

这种题目大概率是使用位运算了
使用异或运算 -无进位相加
异或就是不进行进位的操作，然后进行相加的操作

class Solution {public:int getSum(int a, int b){//进位的结果为0的时候我们就可以获得我们的答案了，我们就停止循环了while(b!=0){int x=a^b;//先算出无进位相加的结果//unsigned是为了避免-1的情况，因为-1的二进制位里面都是1unsigned int carry=(unsigned int)(a&b)<<1;//算出进位//unsigned int处理负数出现的情况a=x;b=carry;}return a;}};

a ^ b 计算无进位相加的结果。
(a & b) << 1 计算进位，并将其移动到正确的位置。
不断进行这个过程，直到没有进位，最终得到加法结果。

37.只出现一次的数字II

题目链接
给你一个整数数组 nums ，除某个元素仅出现一次外，其余每个元素都恰出现 **三次。**请你找出并返回那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。

示例 1：

输入： nums = [2,2,3,2]
输出： 3

示例 2：

输入： nums = [0,1,0,1,0,1,99]
输出： 99

我们是可以使用哈希表进行计数的，可以在表中查找到只出现一次的那个元素
代码如下：

class Solution {public:int singleNumber(vector<int>& nums){/*思路：这个题我有一个思路，利用计数器，先遍历一遍这个数组，然后分别进行计数，如果次数是3的话那么就排除，如果最后遍历完的话次数是2的数那么我们直接返回，*///unordered_map和map的区别：插入、查找、删除操作通常比 map 快，平均时间复杂度为o(1)//对于需要快速查找的场景（例如字典或频次统计），unordered_map 更优。//对于范围查询、按序遍历等操作，map 更适合。//创建一个哈希表进行计数操作unordered_map<int,int>count;//第一个int是这个数//第二个int是这个数出现的次数//遍历数组，对每个数组进行计数操作for(int num:nums){count[num]++;}//遍历哈希表，找到出现次数为1的数字并且进行返回for(auto&entry:count){if(entry.second==1){return entry.first;}}return -1;// 题目保证一定存在结果，所以这里不会到达}};

但是这里的话我们还是使用位运算相关的方法进行解决这个题目

class Solution {public:int singleNumber(vector<int>& nums){int ret = 0; // 用来存储最终的结果for(int i = 0; i < 32; i++) // 依次处理每一位（假设是32位整数）{int sum = 0;//遍历数组中的每个数，计算每个数的二进制位中第i位是否为1，然后进行统计for(int x : nums) // 遍历数组中的每一个数if(((x >> i) & 1) == 1) // 检查数字x的第i位是否为1sum++; // 统计当前数组中的所有数字在第i位为1的次数，sum %= 3; // 由于其他数字都是三次出现的，sum % 3取余，剩下1就是我们要找的数字的第i位if(sum == 1) ret |= 1 << i; // 如果第i位出现了1次，则在结果中设置第i位为1}return ret; // 返回结果}};

我们对每一位进行处理，通过循环，在每次判断中，我们就计算我们所有数中第i位出现的次数，因为有的数出现三次，有的出现一次，所以我们就将每次第i位的总和算出来再来进行模3 的操作，判断最后的结果是多少，如果是0的话，那么就证明我们只出现1次的那个数没有这一位
但是如果最后的余数是1的话，那么就说明那个只出现一位的数里面的第i位有这个数
等待循环结束，我们的判断就结束了，我们直接将最后的结果进行返回就行了

38.消失的两个数字

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

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

示例 1：

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

示例 2：

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

这个题我们还是利用位运算进行解决
我们将这两个数组看成两个整体，那么题目就可以看成，a和b出现过1次，其他的数字出现过两次，然后找出这个出现一次的数

一：将所有的数都异或再一起，tmp最后的结果就是a^ b
二：找到tmp中比特位为1的那一位，因为a和b是不一样的，所以结果是绝对不等于0的，相同为0，相异为1
找到第x位为1 的那一位
然后的话我们a和b的第x位一个是0，一个是1
那么我们再将原来的两个数组分成下面的这样子

左边的异或的结果就是a，右边的异或结果就是b了

第三步就是：根据x位的不同，划分为两类异或

class Solution {public:vector<int> missingTwo(vector<int>& nums){//1.将所有的数异或到一起int tmp=0;//存储异或结果for(auto x:nums) tmp^=x;for(int i=1;i<=nums.size()+2;i++) tmp^=i;//这里的数组是包含了缺失的两个数，所以大小会多出2//到这里的话，tmp中存的就是a和b异或的结果了//2.找出a和b中比特位不同的那一位，就是tmp中唯一的那一位int diff=0;while(1){if(((tmp>>diff)&1)==1) break;//说明这一位就是1了else diff++;}//3.根据diff位的不同将所有的数划分为两类来进行异或int a=0,b=0;for(auto x:nums){if(((x>>diff)&1)==1) b^=x;else a^=x;}for(int i=1;i<=nums.size()+2;i++){if(((i>>diff)&1)==1) b^=i;else a^=i;}//那么这两个for循环结束之后，a和中存的就是结果了return {a,b};}};

先将缺少ab的数组和不缺少ab的数组进行异或，最后的结果就是我们的ab异或的值
我们根据a和b中比特位不同的那一位，将缺少ab的数组分成两个组，我们找到比特位不同的那一位的位置diff

然后在缺失ab的数组根据这个diff位分为两组进行异或操作，分别存在a和b中，然后再在不缺少ab的数组中进行分组进行同样的异或操作
最后我们的a和b就能被区分出来了

33.常见位运算

1.基础位运算

2.给一个数n，确定他的二进制表示中的第x位是0还是1

3.将一个数n的二进制表示的第x位修改成1

4.将一个数n的二进制表示的第x位修改成0

5.位图

6.提取一个数（n）二进制表示中最右侧的1

7.干掉一个数（n）二进制表示中最右侧的1

8.异或（^）运算的运算律

34.判断字符是否唯一

35.丢失的数字

36.两整数之和

37.只出现一次的数字II

38.消失的两个数字

相关文章：