| 【夜深人静学数据结构与算法 | 您所在的位置：网站首页 › linux运算次方 › 【夜深人静学数据结构与算法 |
【夜深人静学数据结构与算法
|
目录 前言： 位运算符： 解题应用： 231. 2 的幂 - 力扣（LeetCode） 191. 位1的个数 - 力扣（LeetCode） 面试题 16.01. 交换数字 - 力扣（LeetCode） 136. 只出现一次的数字 - 力扣（LeetCode） 461. 汉明距离 - 力扣（LeetCode） 693. 交替位二进制数 - 力扣（LeetCode） 1863. 找出所有子集的异或总和再求和 - 力扣（LeetCode）（重点必看） 总结：
今天我们将带领大家学习位运算符号以及位运算的使用技巧，相信你会惊叹于位运算奇妙的应用场景，感叹于前辈们的脑洞之大。 位运算符：位运算符是一种用于处理二进制位的操作符，主要用于对整数在二进制下的位进行一些特定的运算。 以下是常见的位运算符： &：按位与，对两个操作数的每个二进制位进行与操作，若两个二进制位均为1，则该位结果为1，否则为0。例如：3 & 5 = 1（二进制下为0011 & 0101 = 0001）。|：按位或，对两个操作数的每个二进制位进行或操作，若两个二进制位中至少有一个为1，则该位结果为1，否则为0。例如：3 | 5 = 7（二进制下为0011 | 0101 = 0111）。^：按位异或，对两个操作数的每个二进制位进行异或操作，若两个二进制位不同，则该位结果为1，否则为0。例如：3 ^ 5 = 6（二进制下为0011 ^ 0101 = 0110）。~：按位取反，对操作数的每个二进制位进行取反操作，即0变为1，1变为0。例如：~3 = -4（二进制下为~0011 = 1100）。需要注意的是，取反操作会同时改变符号位，将正数变为负数，负数变为正数。 2 = -1（二进制下为~0011 >> 2 = ~0000 = 1111 = -1）。需要注意的是，位运算符仅适用于整数类型。在使用位运算符时，还需要注意二进制位数的溢出问题。 解题应用： 231. 2 的幂 - 力扣（LeetCode）给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。 如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。 这里的解题思路为：只要一个数字是二的幂次方，那他就一定是100000这种首位为1，后面的都是0的整数。而给他减一后的结果一定是1111111这种，例如8的二进制的1000，那么（8-1）的二进制就是0111.我们可以发现8 &（8-1）等于0. 因此我们可以总结出规律：一个是2的幂次方的数字与比他小于一的数字 位与 的结果一定为0 解题代码： class Solution { public: bool isPowerOfTwo(int n) { return (n>0)&&( n&(n-1) )==0; } }; 191. 位1的个数 - 力扣（LeetCode）编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为汉明重量）。 试例： 输入：n = 00000000000000000000000000001011 输出：3 解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。 其实我们可以快速的得出思路：不断的让n与n-1进行位与运算，将运算结果赋值给n并进行下一次计算，直到n等于0，添加计数器统计循环次数，之后返回计数器，就可以得到正确答案。 我们以统计二进制数字111为例： 第一次：此时n等于111，111与110进行 位与 运算，结果为110。 第二次：此时n等于110，110与101进行 位与 运算，结果为100。 第三次：此时n等于100，100与011进行 位与 运算，结果为0. 循环结束，一共进行了三次循环，因此输出count=3。 代码： class Solution { public: int hammingWeight(uint32_t n) { int count=0; while(n>0) { n=n&(n-1); count++; } return count; } }; 面试题 16.01. 交换数字 - 力扣（LeetCode）编写一个函数，不用临时变量，直接交换numbers = [a, b]中a与b的值。 这里就用到了两条性质：a ^ a = 0; a ^ 0 = a; 代码： class Solution { public: vector swapNumbers(vector& numbers) { numbers[0]= numbers[0]^ numbers[1]; numbers[1]=numbers[1]^ numbers[0]; numbers[0]= numbers[0]^ numbers[1]; return numbers; } };我们用a和b代替两个待交换的变量解释一下核心代码：a = a ^ b b = a ^ b = a ^ b ^ b = a ^ 0 = a a = a ^ b = a ^ b ^ a = a ^ a ^ b = b 看懂了这三个式子，就可以轻松的学会不建立临时变量还可以交换数字 136. 只出现一次的数字 - 力扣（LeetCode）给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。 你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。 解题思路：这题还是利用异或运算，因为如果其他元素均出现两次，那么就这个数组的格式我们可以概括为[a,a,b,b,c,c,d,d,r]。那么两个相同的数字异或和为0，零异或任何数都等于它本身。因此我们可以利用这一点，对数组的所有数字进行异或运算遍历，最后的结果就是只出现一次的数字。 class Solution { public: int singleNumber(vector& nums) { int sum=nums[0]; for(int i=1;i0) { z=z&(z-1); count++; } return count; } }; 693. 交替位二进制数 - 力扣（LeetCode）给定一个正整数，检查它的二进制表示是否总是 0、1 交替出现：换句话说，就是二进制表示中相邻两位的数字永不相同。 
解题思路：如果总是010101010101010这种交替出现，那我们从最低位开始，每一次判断两位。如果始终都是10或者01这种那么就说明这是一个交替位二进制数字。为了方便判断，我们始终每一次进行判断之后，都让待判断数字右移两位，这样我们就是始终在与末尾两位数字进行判断，因为末尾如果符合条件不是01就是10，我们可以判断他与3位与的结果是否为两个恒定的值，但是这样太过于麻烦，我们可以转换一下思路：不符合条件的只有00或者11，00 & 11（3）的结果为0，11&11（3）=3，那么我们只需要判断如果有0或者3，就return false。我们可以根据此进行判断。 class Solution { public: bool hasAlternatingBits(int n) { while(n) { if((n&3)==3 || (n&3)==0) { return f } } } }; 1863. 找出所有子集的异或总和再求和 - 力扣（LeetCode）（重点必看）一个数组的 异或总和 定义为数组中所有元素按位 XOR 的结果；如果数组为 空 ，则异或总和为 0 。 例如，数组 [2,5,6] 的 异或总和 为 2 XOR 5 XOR 6 = 1 。 给你一个数组 nums ，请你求出 nums 中每个 子集 的 异或总和 ，计算并返回这些值相加之 和 。 注意：在本题中，元素 相同 的不同子集应 多次 计数。 数组 a 是数组 b 的一个 子集 的前提条件是：从 b 删除几个（也可能不删除）元素能够得到 a 。
解题思路：其实本道题的难点在于如何求出一个集合的所有子集 思路：在一个集合中，所有元素在取子集的时候都只有两种状态：取或不取，我们可以把他对应到二进制中的0和1，那么每一个子集都有自己的一个二进制数字。 nums=[1 , 2 , 3 ] 子集有 1.[不取 , 不取, 不取]-------->(0,0,0,)----->000=0 2.[不取，不取，取 ]-------->(0,0,1)------ >001=1 3.[不取， 取，不取]-------->(0,1,0)------->010=2 4.[不取， 取， 取]-------->(0,1,1)------ >011=3 5.[取，不取， 不取]-------->(1,0,0)------->100=4 4.[取 ， 不取， 取]-------->(1,0,1)-------->101=5 5.[取， 取， 不取]-------->(1,1,0)-------->110=6 5.[取 ， 取 ， 取]--------->(1,1,1)------ >111=7 我们可以看出每一个子集的状态都有一个对应的二进制，这个二进制最小是0（所有位置都不取），最大是7（所有位置都取）。而我们可以遍历所有的符合要求的二进制数字，判断每一个位置上是否为1，1取0不取，这样我们就得到了一个集合的所有子集 这里我们就记住一个式子：i &（1 |
【本文地址】