目录
- 基础
- 经典例题
- [面试题 01.01. 判定字符是否唯一](https://leetcode.cn/problems/is-unique-lcci/description/)
- [268. 丢失的数字](https://leetcode.cn/problems/missing-number/description/)
- [371. 两整数之和](https://leetcode.cn/problems/sum-of-two-integers/description/)
- [137. 只出现一次的数字 II](https://leetcode.cn/problems/single-number-ii/description/)
- [面试题 17.19. 消失的两个数字](https://leetcode.cn/problems/missing-two-lcci/description/)
基础
基本的位运算符有：
<< >> ^ ~ & |
对于这些位运算之间的优先级没有必要记忆，统一加括号即可。
异或操作就是进行无进位相加，有以下规律：
a^0=a
a^a=0
a^b=b^a
a^b^a=b
下面总结一下使用这些位运算符常见的操作：
- 求一个整数n的二进制位的第x（0开始）个比特位是0还是1
(n>>x)&1
- 将一个整数的二进制位的第x位改为0
n=n&(~(1<<x))
- 将一个整数的二进制位的第x位改为1
n=n|(1<<x)
- 提取出整数n最右侧的1
n=n&(-n)
取负数后，最右侧的1所在位置左侧的比特位都取反了，右侧的及当前位置的比特位数保持不变，且右侧位置的比特位全是0
- 去除整数n最右侧的1
n=n&(n-1)
n-1会向n中最右侧的1借1，从而将其置0，该位置左侧的比特位保持不变，右侧比特位全置1，且在n中该位置右侧比特位是全0
- 位图
使用一个比特位（也可以多个）标识数据的状态，要根据具体问题实现
经典例题
面试题 01.01. 判定字符是否唯一
实现一个算法，确定一个字符串 s 的所有字符是否全都不同。
0 <= len(s) <= 100
s[i]仅包含小写字母
如果你不使用额外的数据结构，会很加分。
解法一：使用一个哈希表
解法二：使用一张位图，由于只有26个字符，因此使用一个32位整型类型作为位图即可
class Solution {
public:bool isUnique(string astr) {if(astr.size() > 26){return false;} int bitMap = 0;int i = 0;for (; i < astr.size(); ++i) {int tmp = 1 << (astr[i] - 'a');if (bitMap & tmp) {return false;}bitMap |= tmp;}return true;}
};
268. 丢失的数字
给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。
解法一：利用等差数列求和公式对[0,n]求和得到sum，sum在减去nums的和即可
class Solution {
public:int missingNumber(vector<int>& nums) {long long int sum1=(nums.size()*(1+nums.size()))/2.0;long long int sum2=0;for(auto e:nums){sum2+=e;}return sum1-sum2;}
};
解法二：利用规律a^a=0，a^0=a，先对[0,n]一一异或得到tmp，再用tmp和nums一一异或即可得到缺失的数字
int missingNumber(int* nums, int numsSize)
{int missnum=0;int i=numsSize+1;while(i--){missnum^=i;}i=numsSize;while(i--){missnum^=nums[i];}return missnum;
}
371. 两整数之和
给你两个整数 a 和 b ，不使用 运算符 + 和 - ，计算并返回两整数之和。
解法1：利用位运算符模拟二进制加法过程
class Solution {
public:int getSum(int a, int b) {int ans=0;int tmp=0;//进位int i=0;for(;i<32;++i){int t1=1&(a>>i);int t2=1&(b>>i);if((t1||t2||tmp)&&(!((t1&&t2&&!tmp)||(tmp&&t2&&!t1)||(tmp&&t1&&!t2)))){ans|=1<<i;tmp=0;}if((t1&&t2)||(t1&&tmp)||(t2&&tmp)){tmp=1;}}return ans;}
};
解法二：a^b就得到a和b的无进位相加m，(a&b)<<1就得到a和b的进位n，可以令a=m，b=n，重复以上过程，直到进位n为0为止
class Solution {
public:int getSum(int a, int b) {while(b){int m=a^b;int n=(a&b)<<1;a=m;b=n;}return a;}
};
137. 只出现一次的数字 II
给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。
记录所有的整数对应的比特位为1的频率，将这些频率进行模3运算，得到的就是只出现一次的整数对应的比特位
class Solution {
public:int singleNumber(vector<int>& nums) {vector<int> bit(32,0);int i=0;for(;i<nums.size();++i){int j=0;for(;j<32;++j){bit[31-j]+=1&(nums[i]>>j);bit[31-j]%=3;}}int ans=0;for(i=0;i<32;++i){ans|=bit[i]<<(31-i);}return ans;}
};
面试题 17.19. 消失的两个数字
给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？
以任意顺序返回这两个数字均可。
假设缺的数字是a和b，先对[1,N]异或得到tmp，再用tmp对数组nums一一异或得到的结果就是a^b，由于a和b是不同的两个数字，那么a^b一定有一个比特位为1，假设a^b的第x个比特位为1，现在[0,N]分为第x个比特位为0和为1的两组数字tmp1和tmp2，再将数组nums也分为第x个比特位为0和为1的两组数字nums1和nums2，此时将tmp1和nums1的数字一一异或即可得到a，将tmp2和nums2的数字一一异或即可得到b
class Solution {
public:vector<int> missingTwo(vector<int>& nums) {int tmp = 0; // a^bint i = 0;for (i = 1; i <= nums.size() + 2; ++i) {tmp ^= i;}for (i = 0; i < nums.size(); ++i) {tmp ^= nums[i];}// 寻找xint x = 0;while (x < 32) {if (tmp & (1 << x)) {break;}++x;}// 分组得到a和bint a = 0;int b = 0;for (i = 1; i <= nums.size() + 2; ++i) {if (i & (1 << x)) {b ^= i;} else {a ^= i;}}for (i = 0; i < nums.size(); ++i) {if (nums[i] & (1 << x)) {b ^= nums[i];} else {a ^= nums[i];}}return {a, b};}
};
