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

【算法】位运算经典例题

news 2025/8/15 12:24:36

1.常见位运算总结

1.1基础位运算

左移（<<）

规则：
将二进制位整体向左移动 n 位，高位溢出丢弃，低位补 0。
公式：a << n 等价于 a * 2^n（无溢出时）。
示例：
5 << 2（二进制：101 << 2 = 10100），结果为 20（5 × 2² = 20）。
用途：
快速乘法（乘以 2 的幂）；
构建位掩码（如 1 << 3 生成 0b1000）

右移（>>）

规则：
逻辑右移：无符号数，向右移动 n 位，高位补 0，低位丢弃。
算术右移：有符号数，向右移动 n 位，高位补符号位（保持正负不变），低位丢弃。
公式：a >> n 等价于 a / 2^n（向下取整，无溢出时）。
示例：
无符号数 8 >> 2（1000 >> 2 = 0010），结果为 2；
有符号数 -8 >> 2（假设 8 位补码 11111000 >> 2 = 11111110），结果为 -2。
有符号数以补码形式存储，8 位有符号数的范围是 -128 ~ 127。
正数的补码 = 原码（二进制本身）；
负数的补码 = 原码（符号位不变）取反 + 1（末位加 1）。
用途：
快速除法（除以 2 的幂）；
提取高位数据（如 (num >> 4) & 0x0F 提取高 4 位）。

按位与（&）运算

规则：两个对应位都为 1 时，结果位为 1；否则为 0。
示例：5 & 3 的计算（二进制：101 & 011 = 001），结果为 1。
记忆口诀：有0就是0

按位或（|）运算

规则：两个对应位中至少有一个为 1 时，结果位为 1；否则为 0。
示例：5 | 3 的计算（二进制：101 | 011 = 111），结果为 7。
记忆口诀：有1就是1

按位异或（^）

规则：两个对应位不同时，结果位为 1；相同则为 0。
示例：5 ^ 3 的计算（二进制：101 ^ 011 = 110），结果为 6。
记忆口诀：
1.相同为0，相异为1
2.无进位相加：
将二进制数对应位按加法规则相加，结果超出1 产生进位就不进位并且将当前位置0，简单说就是出现两次的数相消为0，决定了异或运算具有交换律(本质是出现偶数次的数相消，奇数次保留)

按位取反（~）

规则：将二进制位 0 变为 1，1 变为 0（单目运算）。
示例：~5 的计算（假设为 8 位：~00000101 = 11111010），结果为 -6（补码表示）。

1.2确定数n二进制表示中的第x位是0还是1

既可以将原数右移，也可以将计算数左移再进行位运算

1.3将数n的二进制表示的第x位修改成1

1.因为只能将第x位修改其他位置保持不变，所以移动操作数来计算，原数不动
2.或运算规则有1则为1，操作数不会影响原数，计算结果由原数决定

1.4将数n的二进制表示的第x位修改成0

分析过程与上题一模一样

1.5位图的思想

位图（BitMap）思想是一种利用二进制位（bit）的 0/1 状态来标记数据存在性、属性或状态的高效数据结构。它的核心是用 1 个 bit 位表示 1 个数据的状态（如 “存在” 或 “不存在”），结合位运算（与、或、异或、移位等）实现高效的查询、插入、删除等操作。

空间映射：
将一个整数 x 映射到位图中的某个 bit 位。例如，用第 x 位的 1 表示 x 存在，0 表示 x 不存在。
空间效率：
1 个字节（8bit）可表示 8 个整数的状态，相比用数组存储整数，空间效率提升约 32 倍（32 位整数）或 64 倍（64 位整数）

假设需要处理范围为 0~N-1 的整数，位图可通过一个整数数组实现（数组元素为 unsigned int，每个元素占 32bit）：

核心映射关系
对于整数 x，它在数组中的索引为：index = x / 32（每个 unsigned int 管理 32 个 bit）。
它在该索引元素中的位位置为：bit_pos = x % 32（0~31）

解决位运算问题
类型 1：数组去重（保留唯一元素）

场景：给定一个整数数组（元素范围 0~1000），去除重复元素，保留所有出现过的数。
位图解法：用位图标记元素是否出现过，出现过的元素只保留一次

类型 2：查找数组中只出现一次的元素

场景：数组中除一个元素只出现一次外，其余元素均出现两次，找出该元素。
位图解法：利用异或的性质（x^x=0，x0=x），结合位图记录状态。

类型 3：统计范围内的整数个数

场景：统计 [a, b] 区间内出现过的整数个数（已知所有整数范围 0~N）。
位图解法：遍历位图中 a~b 对应的 bit 位，统计为 1 的个数。

类型 4：快速判断两个集合的交集

场景：判断两个整数集合 A 和 B 是否有交集（元素范围 0~1000）。
位图解法：用两个位图分别标记 A 和 B 的元素，通过位与（&）操作判断是否有同时为 1 的位（即交集）。

1.6提取数n二进制表示中的最右侧的1

1.7干掉数n二进制表示中的最右侧的1

1.8位运算的优先级

位运算的优先级较低，低于算术运算（如 +、*）和关系运算（如 <、==）
能加括号就加括号，方便省事不用记忆绝不出错

2. (191.)位1的个数

在这里插入图片描述

法1：循环检查二进制位

直接循环检查给定整数 n 的二进制位的每一位是否为 1。具体代码中，当检查第 i 位时，我们可以让 n 与 2^i进行与运算，当且仅当 n 的第 i 位为 1 时，运算结果不为 0。

class Solution {
public:int hammingWeight(uint32_t n) {int ret = 0;for (int i = 0; i < 32; i++) {if (n & (1 << i)) {ret++;}}return ret;}
};

法2：位运算优化

运用1.7中总结的公式，将数n最低位的1依次变为0，位1的个数可等价转为执行该公式多少次

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

3. (338.)比特位计数

在这里插入图片描述

同样采取1.7中不断去除最低位1，通过计算次数来确定一个数的二进制位有多少个1，该题给定一个连续数的范围，在计算的外围还要套一层循环来表示数的范围来一次进行计算

class Solution {
public:vector<int> countBits(int n) {vector<int> ret(n+1);for(int i=0;i<=n;i++){int num=0;//用临时变量来替代i计算，避免i被修改int x=i;while(x){x&=x-1;num++;}ret[i]=num;}return ret;}
};

4. (461.汉明距离)

在这里插入图片描述

目标是求两数的二进制位有多少位是不同的，可以先用异或运算进行转化，相同为0相异为1，最终再运用1.7中公式计算这个数中有多少位是1就代表原两数中有多少位不同

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

5. (260.)只出现一次的数字III

在这里插入图片描述

1.因为数组其他元素均出现两次，异或后会相互抵消，剩下结果就是两个目标元素的异或结果
2.int x=(sum==INT_MIN?INT_MIN:sum&(-sum));
该运算能保留最低位的1，其余位变为0，因为a、b异或结果不为0在这一位上必然一个为0一个为1，所以可以用这一位作为分组依据；该表达式还有防溢出的作用，对 INT_MIN 取负数的操作上就是补码取反再加1，INT_MIN 是 int 能表示的最小负数：-2147483648（二进制补码为 10000000 00000000 00000000 00000000），在 C++ 中，对 INT_MIN 取负会导致有符号整数溢出，这属于 “未定义行为”，因为整数取值范围为左闭右开，所以等于 INT_MIN 取负结果就溢出，所以当 sum 是 INT_MIN 时，直接将 x 赋值为 INT_MIN（无需计算 -sum，避免溢出）
3.用x（最低位的 1）对所有元素分组，最终结果会被分到不同组

class Solution {
public:vector<int> singleNumber(vector<int>& nums) {int sum=0;for(auto e:nums) sum^=e;//位的分组表示+防止溢出int x=(sum==INT_MIN?INT_MIN:sum&(-sum));//分组遍历找到不同的两个数int num1=0,num2=0;for(auto e:nums){if(e&x) num1^=e;else num2^=e;}return {num1,num2};}
};

5. (260.)只出现一次的数字II

在这里插入图片描述

class Solution {
public:int singleNumber(vector<int>& nums) {int ret=0;for(int i=0;i<=31;i++)//处理32位整数的每一位{int total=0;//统计第i位的总大小for(auto num:nums){total+=((num>>i)&1);}if(total%3==1){ret|=(1<<i);}}return ret;}
};

思路：
对于数组中出现三次的元素，它们的每个二进制位（0 或 1）也会出现三次；而唯一出现一次的元素，其二进制位会让对应位置的总计数 “无法被 3 整除”。通过统计每个二进制位（0~31 位，对应 32 位整数）的出现次数，若某一位的总次数模 3 余 1，则说明该位是目标元素的二进制中为 1 的位。
也可以用哈希表但空间复杂度为O(N)

6. ⾯试题 01.01. 判定字符是否唯⼀

在这里插入图片描述

算法思路：
利⽤位图的思想，每⼀个⽐特位代表⼀个字符，⼀个 int 类型的变量的 32 位⾜够表⽰所有的⼩写字⺟。⽐特位⾥⾯如果是 0 ，表⽰这个字符没有出现过。⽐特位⾥⾯的值是 1 ，表⽰该字符出现过。那么我们就可以⽤⼀个整数来充当哈希表。

class Solution
{
public:bool isUnique(string astr) {// 利⽤鸽巢原理来做的优化if(astr.size() > 26) return false; int bitMap = 0;for(auto ch : astr){int i = ch - 'a';// 先判断字符是否已经出现过if(((bitMap >> i) & 1) == 1) return false;// 把当前字符加⼊到位图中bitMap |= 1 << i;}return true;}
};

7. (268.) 丢失的数字

在这里插入图片描述

如果我们把数组中的所有数，以及 [0, n] 中的所有数全部异或在⼀起，那么根据异或运算的「消消乐」规律，最终的异或结果应该就是缺失的数

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

也可以用高斯公式公式计算((nums.size())*(nums.size()+1))/2-sum;

8. (371.)两整数之和

在这里插入图片描述

异或 ^ 运算本质是⽆进位加法；按位与 & 操作能够得到进位；然后⼀直循环进⾏，直到进位变成 0 为⽌。

由于计算的是进位，所以结果要左移一位，同时要将类型强转为无符号整型，因为如果操作数是负数（即符号位为 1），其行为是未定义的

class Solution {
public:int getSum(int a, int b) {while(b){int sum=a^b;//算出无进位相加的结果b=(unsigned int)((a&b)<<1);//算出进位的结果a=sum;}return a;}
};

9. ⾯试题 17.19. 消失的两个数字

在这里插入图片描述

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

class Solution {
public:vector<int> missingTwo(vector<int>& nums) {//异或所有元素，找出消失的两个数字的异或结果int sum=0;for(auto num:nums) sum^=num;for(int i=1;i<=nums.size()+2;i++) sum^=i;//设定比特位标志来分组int x=(sum==INT_MIN?INT_MIN:sum&(-sum));int num1=0,num2=0;//分组计算异或结果for(auto num:nums){if(x&num) num1^=num;else num2^=num;}for(int i=1;i<=nums.size()+2;i++){if(x&i) num1^=i;else num2^=i;}return {num1,num2};}
};