目录
一:位运算符及一些常用结论总结
1.给一个数n，确定它的二进制表示中的第x位是0还是1(位数从右向左0开始增加)
2.将一个数n的二进制表示形式的第x位修改成1
3.将一个数n的二进制表示的第x位修改为0
4.提取一个数n的二进制表示中最右侧的1
5.干掉一个数n的二进制表示中最右侧的1
二:LeetCode OJ练习
1.第一题
2.第二题
3.第三题
4.第四题
5.第五题
一:位运算符及一些常用结论总结
知识传送门 位运算符介绍
1.给一个数n，确定它的二进制表示中的第x位是0还是1(位数从右向左0开始增加)
2.将一个数n的二进制表示形式的第x位修改成1
3.将一个数n的二进制表示的第x位修改为0
4.提取一个数n的二进制表示中最右侧的1
5.干掉一个数n的二进制表示中最右侧的1
二:LeetCode OJ练习
1.第一题
OJ传送门 LeetCode 面试题01.01 判断字符是否唯一
画图分析:
具体代码:
bool isUnique(string str) {int len=str.size();if(len>26) return false;//利用鸽巢原理做优化int bitMap=0;for(auto ch :str){int x=ch-'a';//先判断字符是否已经存在if((bitMap>>x)&1==1) return false;//把当前字符加入到位图中bitMap=bitMap | (1<<x);}return true;}2.第二题
OJ 传送门 LeetCode_268 消失的数字
画图分析;
具体代码:
int missingNumber(vector<int>& nums) {int n=nums.size();int ret=0;for(int i=0;i<=n;++i){ret^=i;}for(auto x:nums){ret^=x;}return ret;}3.第三题
OJ 传送门 LeetCode_371 两整数之和
画图分析:
具体代码:
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;}4.第四题
OJ传送门 LeetCode_137 只出现一次的数字 II
画图分析:
具体代码:
int singleNumber(vector<int>& nums) {int ret=0;for(int i=0;i<32;++i)//依次修改ret的每一位{int sum=0;//统计每个bit位的数组和for(auto x:nums){if(((x>>i)&1)==1) sum++;}if(sum%3==1) ret|=(1<<i);//放入到对应bit位中}return ret;}5.第五题
OJ 传送门 LeetCode 面试题 17.19 消失的两个数字
画图分析:
具体代码:
vector<int> missingTwo(vector<int>& nums) {//1.将所有数据异或在一起int tmp=0,n=nums.size();for(auto x:nums) tmp^=x;for(int i=1;i<=n+2;++i) tmp^=i;//2.寻找bit为1的位置int pos=0;while(1){if(((tmp>>pos)&1)==1) break;else ++pos;}//3.根据此位置将数据分为两组int a=0,b=0;for(auto x:nums){if(((x>>pos)&1)==1) a^=x;else b^=x;}for(int i=1;i<=n+2;++i){if(((i>>pos)&1)==1) a^=i;else b^=i;}return {a,b};}
