【算法题攻略】位运算总结（含习题解析）

文章目录一、位运算总结1. 位操作符 和 移位操作符含原码、反码、补码介绍2. 给一个数n确定它的二进制表示中的第 x 位是 0 还是 13. 给一个数n将它的二进制表示中的第 x 位修改成 1或 04. 提取一个数 n 二进制表示中最右侧的15. 干掉一个数 n 二进制表示中最右侧的16. 异或^运算的运算律二、习题解析1. 判定字符是否唯一位图2. 丢失的数字异或运算3. 两整数之和4. 只出现一次的数字 II比特位计数5. 消失的两个数字hard一、位运算总结1. 位操作符 和 移位操作符含原码、反码、补码介绍1原码、反码、补码介绍整数的2进制表示方法有三种即原码、反码和补码。有符号整数的三种表示⽅法均有符号位和数值位两部分2进制序列中最高位的1位是被当做符号位剩余的都是数值位。符号位都是用0表示“正”用1表示“负”。正整数的原、反、补码都相同。负整数的三种表示方法各不相同如下所示原码直接将数值按照正负数的形式翻译成⼆进制得到的就是原码。反码将原码的符号位不变其他位依次按位取反就可以得到反码。补码反码1就得到补码。补码得到原码也是可以使用取反1的操作。2位操作符:按位与操作符对应bit位 有0就是0都为1才为1|:按位或操作符对应bit位 有1就是1都为0才为0 ^:按位异或操作符对应bit位 相同为0相异为1 / 无进位加法 ~:按位取反操作符单目操作符注他们的操作数必须是整数而且是使用整数在内存中存储的补码形式来进行位操作的使用示例#includestdio.hintmain(){intnum11;intnum2-1;printf(%d\n,num1num2);//1的补码:00000000000000000000000000000001//-1的补码:11111111111111111111111111111111//1-1的结果:00000000000000000000000000000001(每个对应的bit位都为1则该位结果为1否则为0//结果的补码是正整数正整数的原、反、补码都相同所以这也是结果的原码转换成10进制就是1printf(%d\n,num1|num2);//1的补码:00000000000000000000000000000001//-1的补码:11111111111111111111111111111111//1|-1的结果:11111111111111111111111111111111(每个对应的bit位有1则该位结果为1都为0结果才为0//对结果的补码进行转换得到其原码:10000000000000000000000000000001(转换成10进制就是-1)printf(%d\n,num1^num2);//1的补码:00000000000000000000000000000001//-1的补码:11111111111111111111111111111111//1^-1的结果:11111111111111111111111111111110(每个对应的bit位相异则该位结果为1相同则为0//对结果的补码进行转换得到其原码:10000000000000000000000000000010(转换成10进制就是-2)printf(%d\n,~0);//0的补码:00000000000000000000000000000000//~0的结果:11111111111111111111111111111111(把每一个bit位取反//对结果的补码进行转换得到其原码:10000000000000000000000000000001(转换成10进制就是-1)return0;}3移位操作符左移操作符 的作用是对整型变量的补码左移指定位数它的移位规则是左边抛弃、右边补0。它的操作数有2个是一个双目操作符。使用示例#includestdio.hintmain(){intn1;nn1;//1的补码是00000000000000000000000000000001//左移1位变成:00000000000000000000000000000010正整数的原、反、补码都相同所以这也是结果的原码转换成10进制就是2printf(%d\n,n);inti-1;ii1;//-1的补码是11111111111111111111111111111111//左移1位变成:11111111111111111111111111111110(这是结果的补码)//对结果的补码进行取反1的操作得到它的原码:10000000000000000000000000000010(转换成10进制就是-2)printf(%d\n,i);return0;}右移操作符 也是一个双目操作符它的作用是对整型变量的补码右移指定位数 不过它的移位规则分为两种逻辑右移左边用0填充右边丢弃算术右移左边用原该值的符号位填充右边丢弃绝大部分编译器都会采用算数右移的规则后面的举例也采用算术右移使用示例#includestdio.hintmain(){intn1;nn1;//1的补码是00000000000000000000000000000001//右移1位变成:00000000000000000000000000000000正整数的原、反、补码都相同所以这也是结果的原码转换成10进制就是0printf(%d\n,n);inti-1;ii1;//-1的补码是11111111111111111111111111111111//右移1位仍然是:11111111111111111111111111111111(这是结果的补码)//对结果的补码进行取反1的操作得到它的原码:10000000000000000000000000000001(转换成10进制就是-1)printf(%d\n,i);return0;}2. 给一个数n确定它的二进制表示中的第 x 位是 0 还是 1公式( n (x-1) ) 1右移 x-1 位再 13. 给一个数n将它的二进制表示中的第 x 位修改成 1或 0给一个数n将它的二进制表示中的第 x 位修改成 1公式n | ( 1 (x - 1) )给一个数n将它的二进制表示中的第 x 位修改成 0公式n ( ~ 1 (x - 1) ) )4. 提取一个数 n 二进制表示中最右侧的1公式n ( -n )5. 干掉一个数 n 二进制表示中最右侧的1公式n ( n-1 )6. 异或^运算的运算律n ^ 0 nn ^ n 0“消消乐”a ^ b ^ c a ^ ( b ^ c )异或^运算 满足交换律二、习题解析1. 判定字符是否唯一位图题目链接: 面试题 01.01. 判定字符是否唯一题目描述实现一个算法确定一个字符串 s 的所有字符是否全都不同。示例 1输入: s “leetcode”输出: false示例 2输入: s “abc”输出: true限制0 len(s) 100s[ i ]仅包含小写字母如果你不使用额外的数据结构会很加分。代码实现classSolution{public:boolisUnique(string astr){intn0;for(autoctr:astr){if((n(ctr-a))11){returnfalse;}n|(1(ctr-a));}returntrue;}};2. 丢失的数字异或运算题目链接: 268. 丢失的数字题目描述给定一个包含 [0, n] 中 n 个数的数组 nums 找出 [0, n] 这个范围内没有出现在数组中的那个数。示例 1输入nums [3,0,1]输出2解释n 3因为有 3 个数字所以所有的数字都在范围 [0,3] 内。2 是丢失的数字因为它没有出现在 nums 中。示例 2输入nums [9,6,4,2,3,5,7,0,1]输出8解释n 9因为有 9 个数字所以所有的数字都在范围 [0,9] 内。8 是丢失的数字因为它没有出现在 nums 中。提示n nums.length1 n 10^40 nums[i] nnums 中的所有数字都 独一无二进阶你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题代码实现classSolution{public:intmissingNumber(vectorintnums){intresult0;inti0;for(;inums.size();i){result^(nums[i]^i);}result^i;returnresult;}};3. 两整数之和题目链接: 371. 两整数之和题目描述给你两个整数 a 和 b 不使用 运算符 和 - ​​​​​​​计算并返回两整数之和。示例 1输入: a 1, b 2输出: 3示例 2输入: a 2, b 3输出: 5提示-1000 a, b 1000代码实现classSolution{public:intgetSum(inta,intb){intsum0;intcarry0;do{suma^b;// 无进位加法carry(ab)1;// 进位值asum,bcarry;}while(carry);// 进位值为0结束returnsum;}};4. 只出现一次的数字 II比特位计数题目链接: 137. 只出现一次的数字 II题目描述给你一个整数数组 nums 除某个元素仅出现 一次 外其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。示例 1输入: nums [2,2,3,2]输出: 3示例 2输入: nums [0,1,0,1,0,1,99]输出: 99提示1 nums.length 3 * 10^4-2^31 nums[ i ] 2^31 - 1nums 中除某个元素仅出现 一次 外其余每个元素都恰出现 三次代码实现classSolution{public:intsingleNumber(vectorintnums){intret0;for(inti0;i32;i)// 依次去修改 ret 中的每⼀位{intcount0;for(autoit:nums)// 计算nums中所有的数的第 i 位的和{count(iti)1;}countcount%3;if(count1){ret|(1i);}}returnret;}};5. 消失的两个数字hard题目链接: 面试题 17.19. 消失的两个数字题目描述给定一个数组包含从 1 到 N 所有的整数但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗以任意顺序返回这两个数字均可。示例 1输入: [1]输出: [2, 3]示例 2输入: [2, 3]输出: [1, 4]提示nums.length 30000代码实现classSolution{public:vectorintmissingTwo(vectorintnums){intsizenums.size()2;intExclusive_OR0;// 将原数组 和 补上两个缺失的数的数组 一起进行异或运算for(inti1;isize;i){Exclusive_OR^i;}for(autoit:nums){Exclusive_OR^it;}// 提取异或结果的二进制表示中最右侧的1intlowbitExclusive_OR(-Exclusive_OR);inta0;intb0;for(inti1;isize;i){if((ilowbit)0)// 划分成两部分进行异或运算a^i;elseb^i;}for(autoit:nums){if((itlowbit)0)// 划分成两部分进行异或运算a^it;elseb^it;}vectorintvec{a,b};returnvec;}};