优选算法之位运算
目录
一、常见位运算总结
1.基础位运算
2.给定一个数 n，确定它的二进制表示中的第 x 位是 0 还是 1
3.将一个数 n 的二进制表示的第 x 位修改成1
4.将一个数 n 的二进制表示的第 x 位修改成 0
5.提取一个数 n 二进制表示中最右侧的1
6.干掉一个数 n 二进制表示中最右侧的 1
7.位运算的优先级
8.异或(^)运算的运算律
二、判断字符是否唯一
1.题目链接：面试题 01.01. 判定字符是否唯一
2.题目描述：
3.解法（位图的思想）
🌴算法思路：
🌴算法代码：
三、丢失的数字
1.题目链接：268. 丢失的数字
2.题目描述：
3.解法（位运算）
🌴算法思路：
🌴算法代码：
四、 两整数之和
1.题目链接：371. 两整数之和
2.题目描述：
3.解法（位运算）
🌴算法思路：
🌴算法代码：
五、只出现一次的数字II
1.题目链接：137. 只出现一次的数字 II
2.题目描述：
3.解法（比特位计数）
🌴算法思路：
🌴算法代码：
六、消失的两个数字
1.题目链接：面试题 17.19. 消失的两个数字
2.题目描述：
3.解法（位运算）
🌴算法思路：
🌴算法代码：
七、位1的个数
1.题目链接：191. 位1的个数
2.题目描述：
3.解法（位运算）
🌴算法思路：
🌴算法代码：
一、常见位运算总结
1.基础位运算
位运算是直接对整数在内存中的二进制表示进行操作的运算。这些运算通常非常高效，因为它们是在硬件级别执行的。以下是几种基本的位运算符及其用法：
1. 按位与（`&`）
- 当两个相应的二进制位都是1时，结果为1；否则为0。
- 记忆：有 0 就是 0（看这个符号中间是不是有两个 0）
- 例如，`5 & 3` 的结果是 `1`，因为 `5` 在二进制中是 `101`，而 `3` 是 `011`。
2. 按位或（`|`）
- 当两个相应的二进制位中至少有一个是1时，结果为1；否则为0。
- 记忆：有 1 就是 1（看这个符号像不像数字 1）
- 例如，`5 | 3` 的结果是 `7`，因为 `5` 在二进制中是 `101`，而 `3` 是 `011`。
3. 按位异或（`^`）
- 当两个相应的二进制位不同时，结果为1；相同时为0。
- 记忆：(1)相同为0，相异为1；
- (2)无进位相加。
- 例如，`5 ^ 3` 的结果是 `6`，因为 `5` 在二进制中是 `101`，而 `3` 是 `011`。
4. 按位取反（`~`）
- 将每个二进制位反转，1变成0，0变成1。
- 例如，`~5` 的结果取决于你的系统是使用补码表示负数还是符号加绝对值表示法。在大多数现代计算机上，它将返回 `-6`。
5. 左移（`<<`）
- 将一个二进制位模式向左移动指定的位数。
- 例如，`5 << 1` 的结果是 `10`，因为 `5` 在二进制中是 `101`，左移一位后变成 `1010`。
6. 右移（`>>`）
- 将一个二进制位模式向右移动指定的位数。
- 例如，`5 >> 1` 的结果是 `2`，因为 `5` 在二进制中是 `101`，右移一位后变成 `10`。
2.给定一个数 n，确定它的二进制表示中的第 x 位是 0 还是 1
3.将一个数 n 的二进制表示的第 x 位修改成1
4.将一个数 n 的二进制表示的第 x 位修改成 0
5.提取一个数 n 二进制表示中最右侧的1
6.干掉一个数 n 二进制表示中最右侧的 1
7.位运算的优先级
从高到底依次为：
- 按位取反 (
~) > 位移运算符 (<<,>>) > 按位与 (&) > 按位异或 (^) > 按位或 (|)- 如果记不住那就只需要记住能加括号就加括号
注意：这些运算符的优先级通常低于算术运算符（如 加法+ 和 乘法
*），但高于赋值运算符（如=,+=,&=等）。
8.异或(^)运算的运算律
二、判断字符是否唯一
1.题目链接：面试题 01.01. 判定字符是否唯一
2.题目描述：
实现一个算法，确定一个字符串
s的所有字符是否全都不同。示例 1：
输入: s = "leetcode" 输出: false示例 2：
输入: s = "abc" 输出: true限制：
0 <= len(s) <= 100s[i]仅包含小写字母- 如果你不使用额外的数据结构，会很加分。
3.解法（位图的思想）
🌴算法思路：
利用「位图」的思想，每⼀个「比特位」代表一个 字符，一个 int 类型的变量的 32 位足够表示所有的小写字母。比特位里面如果是 0 ，表示这个字符没有出现过。比特位里面的值是 1 ，表示该字符出现过。
那么我们就可以用⼀个「整数」来充当「哈希表」。
🌴算法代码：
class Solution
{
public:int hammingWeight(uint32_t n) {int ret = 0;while(n){n &= (n - 1);ret++;}return ret;}
};三、丢失的数字
1.题目链接：268. 丢失的数字
2.题目描述：
给定一个包含
[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 中。示例 4：
输入：nums = [0] 输出：1 解释：n = 1，因为有 1 个数字，所以所有的数字都在范围 [0,1] 内。1 是丢失的数字，因为它没有出现在 nums 中。
3.解法（位运算）
🌴算法思路：
设数组的大小为 n ，那么缺失之前的数就是 [0, n] ，数组中是在 [0, n] 中缺失一个数形成的序列。
如果我们把数组中的所有数，以及 [0, n] 中的所有数全部「异或」在⼀起，那么根据「异或」运算的「消消乐」规律，最终的异或结果应该就是缺失的数~
🌴算法代码：
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;}
};四、 两整数之和
1.题目链接：371. 两整数之和
2.题目描述：
给你两个整数
a和b，不使用 运算符+和-，计算并返回两整数之和。示例 1：
输入：a = 1, b = 2 输出：3示例 2：
输入：a = 2, b = 3 输出：5
3.解法（位运算）
🌴算法思路：
- 异或 ^ 运算本质是「无进位加法」；
- 按位与 & 操作能够得到「进位」；
- 然后⼀直循环进行，直到「进位」变成 0 为止。
🌴算法代码：
class Solution
{
public:int getSum(int a, int b) {while(b){int x = a ^ b;// 计算无进位相加的结果unsigned int carry = (unsigned int)(a & b) << 1;// 算出进位a = x;b = carry;}return a;}
};五、只出现一次的数字II
1.题目链接：137. 只出现一次的数字 II
2.题目描述：
给你一个整数数组
nums，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。
示例 1：
输入：nums = [2,2,3,2] 输出：3示例 2：
输入：nums = [0,1,0,1,0,1,99] 输出：99
3.解法（比特位计数）
🌴算法思路：
设要找的数为 ret 。
由于整个数组中，需要找的元素只出现了「⼀次」，其余的数都出现的「三次」，因此我们可以根据所有数的「某⼀个比特位」的总和 %3 的结果，快速定位到 ret 的「⼀个比特位上」的值是 0 还是 1 。
这样，我们通过 ret 的每⼀个比特位上的值，就可以将 ret 给还原出来。
🌴算法代码：
class Solution
{
public:int singleNumber(vector<int>& nums) {int ans = 0;for (int i = 0; i < 32; ++i) {int total = 0;for (int num: nums) total += ((num >> i) & 1);if (total % 3 == 1) ans |= (1 << i);}return ans;}
};六、消失的两个数字
1.题目链接：面试题 17.19. 消失的两个数字
2.题目描述：
给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？
以任意顺序返回这两个数字均可。
示例 1:
输入: [1] 输出: [2,3]示例 2:
输入: [2,3] 输出: [1,4]
3.解法（位运算）
🌴算法思路：
本题就是 268. 丢失的数字 + 260. 只出现一次的数字 III 组合起来的题。
先将数组中的数和 [1, n + 2] 区间内的所有数「异或」在一起，问题就变成了：有两个数出现了「⼀次」，其余所有的数出现了「两次」。进而变成了 260. 只出现一次的数字 III 这道题。
🌴算法代码：
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. 找出 a，b 中⽐特位不同的那⼀位int diff = 0;while (1) {if (((tmp >> diff) & 1) == 1)break;elsediff++;}// 3. 根据 diff 位的不同，将所有的数划分为两类来异或int a = 0, b = 0;for (int x : nums)if (((x >> diff) & 1) == 1)b ^= x;elsea ^= x;for (int i = 1; i <= nums.size() + 2; i++)if (((i >> diff) & 1) == 1)b ^= i;elsea ^= i;return {a, b};}
};七、位1的个数
1.题目链接：191. 位1的个数
2.题目描述：
编写一个函数，获取一个正整数的二进制形式并返回其二进制表达式中 设置位 的个数（也被称为汉明重量）。
示例 1：
输入：n = 11 输出：3 解释：输入的二进制串 1011 中，共有 3 个设置位。示例 2：
输入：n = 128 输出：1 解释：输入的二进制串 10000000 中，共有 1 个设置位。示例 3：
输入：n = 2147483645 输出：30 解释：输入的二进制串 11111111111111111111111111111101 中，共有 30 个设置位。
3.解法（位运算）
🌴算法思路：
观察这个运算：n & (n−1)，其运算结果恰为把 n 的二进制位中的最低位的 1 变为 0 之后的结果。
这样我们可以利用这个位运算的性质加速我们的检查过程，在实际代码中，我们不断让当前的 n 与 n−1 做与运算，直到 n 变为 0 即可。因为每次运算会使得 n 的最低位的 1 被干掉，因此运算次数就等于 n 的二进制位中 1 的个数。
🌴算法代码：
class Solution
{
public:int hammingWeight(uint32_t n) {int ret = 0;while(n){n &= (n - 1);ret++;}return ret;}
};