C++优选算法五 位运算
一、位运算
位运算（Bitwise Operations）是直接在整数的二进制表示上进行的操作。这些操作包括位与（AND）、位或（OR）、位非（NOT）、位异或（XOR）、左移（Left Shift）和右移（Right Shift）等。位运算在处理低级别数据、优化性能、实现加密算法等方面非常有用。以下是这些操作的详细介绍：
- 位与（Bitwise AND, &）：
- 对应位都为1时，结果位才为1，否则为0。
- 示例：
5 & 3，二进制表示为101 & 011，结果为001，即1。
- 位或（Bitwise OR, |）：
- 对应位只要有一个为1，结果位就为1。
- 示例：
5 | 3，二进制表示为101 | 011，结果为111，即7。
- 位非（Bitwise NOT, ~）：
- 将每一位取反，0变为1，1变为0。
- 示例：
~5，二进制表示为~101，结果为010（注意，这是补码表示，实际结果取决于整数表示方式，如8位二进制表示则为...1111010，即-6）。
- 位异或（Bitwise XOR, ^）：
- 对应位不同则结果为1，相同则结果为0。
- 示例：
5 ^ 3，二进制表示为101 ^ 011，结果为110，即6。
- 左移（Left Shift, <<）：
- 将二进制位向左移动若干位，右边补0。
- 示例：
5 << 1，二进制表示为101 << 1，结果为1010，即10。
- 右移（Right Shift, >>）：
- 将二进制位向右移动若干位，对于无符号整数，左边补0；对于有符号整数，左边补符号位（即保持正负性）。
- 示例：
5 >> 1，二进制表示为101 >> 1，结果为010，即2。
应用场景
- 性能优化：位运算通常比算术和逻辑运算更快，因为它们直接在硬件层面实现。
- 权限控制：在操作系统中，权限控制经常通过位掩码（bitmask）实现，每个权限对应一个位。
- 图形处理：位运算在图形处理中非常常见，如颜色编码、图像压缩等。
- 加密算法：一些加密算法（如DES、AES）依赖于复杂的位运算。
注意事项
- 整数表示：不同编程语言和平台对整数的表示（如位数、有符号/无符号）可能不同，这会影响位运算的结果。
- 溢出：左移操作可能导致数值溢出，特别是当移位次数超过整数的位数时。
- 符号扩展：右移操作对于有符号整数时，需要注意符号扩展（sign extension），即保持数值的符号不变。
通过理解和应用位运算，可以编写出更高效、更紧凑的代码，特别是在处理底层数据和算法优化时。
二、示例题目
1.判断字符是否唯一. - 力扣（LeetCode）
实现一个算法，确定一个字符串 s 的所有字符是否全都不同。
示例 1：
输入: s= "leetcode" 输出: false
示例 2：
输入: s= "abc" 输出: true
解法(位图的思想）
算法思路:
利用「位图」的思想，每一个「比特位」代表一个「字符，一个 int 类型的变量的 32 位足够表示所有的小写字母，比特位里面如果是0，表示这个字符没有出现过。比特位里面的值是1，表示该字符出现过。
那么我们就可以用一个「整数」来充当 「哈希表」。
class Solution {
public:
bool isUnique(string astr)
{
if(astr.size()>26)
return false;
int bit=0;
for(char ch:astr)
{
int i=ch-'a';
//判断字符是否出现过
if(bit>>i&1==1)
return false;
//把当前字符加入到位图中
bit|=(1<<i);
}
return true;
}
};2.丢失的数字. - 力扣（LeetCode）
给定一个包含 [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，那么缺失之前的数就是在[0，n]，数组中是在 [0,n] 缺失一个数形成的序列。
如果我们把数组中的所有数以及 [0,n] 中的所有数全部「异或」在一起，那么根据「异或」运算的「消消乐」规律，最终的异或结果应该就是缺失的数。
class Solution {
public:
int missingNumber(vector<int>& nums)
{
int bit=0;
for(int i=0;i<nums.size();i++)
{
bit^=nums[i];
}
for(int i=0;i<=nums.size();i++)
{
bit^=i;
}
return bit;
}
};3.两整数之和. - 力扣（LeetCode）
给你两个整数 a 和 b ，不使用 运算符 + 和 - ，计算并返回两整数之和。
示例 1：
输入：a = 1, b = 2 输出：3
示例 2：
输入：a = 2, b = 3 输出：5
解法(位运算):
算法思路:
- 异或 ^运算本质是「无进位加法」;
- 按位与 &操作能够得到「进位」;
然后一直循环进行，直到「进位」变成 0为止。
class Solution {
public:
int getSum(int a, int b)
{
int num=a^b;//无进位相加结果
int sum=a&b;//算出进位
while(sum!=0)
{
sum<<=1;
int n = num;
num^=sum;
sum&=n;
}
return num;
}
};4.只出现一次的数字Ⅱ. - 力扣（LeetCode）
给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。
示例 1：
输入：nums = [2,2,3,2] 输出：3
示例 2：
输入：nums = [0,1,0,1,0,1,99] 输出：99
解法(比特位计数):
算法思路:
设要找的数为ret。
由于整个数组中需要找的元素只出现「一次」，其余的数都出现的「三次」，因此我们可以根据据所有数的「某一个比特位」的总和 % 3，的结果，快速定位到ret的「一个比特位上」的值是 0 还是 1。
这样，我们通过的每一个比特位的值，就可以将 ret 给还原出来。
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ret=0;
for(int i=0;i<32;i++)//依次去修改ret中的每一位比特位
{
int sum=0;
for(int x:nums)//计算nums中所有的数的第i位的和
{
if(((x>>i)&1)==1)
sum++;
}
sum%=3;
if(sum==1)
ret|=1<<i;
}
return ret;
}
};