异或的用途 约定不等于承诺〃 2021-09-27 05:28 427阅读 0赞 > 正式进入高深的算法之前,我们先来学些小技巧。本章拿异或开刀,你会发现一些很有趣的东西。 # 异或的性质 # 异或是一种基于二进制的位运算,用符号XOR或者 ^ 表示,其运算法则是对运算符两侧数的每一个二进制位,同值取0,异值取1。它与布尔运算的区别在于,当运算符两侧均为1时,布尔运算的结果为1,异或运算的结果为0。 简单理解就是不进位加法,如1+1=0,,0+0=0,1+0=1。 性质 1、交换律 可任意交换运算因子的位置,结果不变 2、结合律(即(a^b)^c == a^(b^c)) 3、对于任何数x,都有x^x=0,x^0=x,同自己求异或为0,同0求异或为自己 4、自反性 A ^ B ^ B = A ^ 0 = A ,连续和同一个因子做异或运算,最终结果为自己 # 例一:不引入第三个变量,交换两个变量(整数)的值 # `// 假设存在 a b 两个整数` `a = a^b` `b = a^b` `a = a^b` 是不是很神奇,如果不理解,请仔细推算,推算完后脑洞会开一点吧。 # 例二:判断奇偶数更简单高效的做法 # 奇数二进制的最低位一定是1,偶数二进制的最低位一定是0,所以 `a^1==1?偶数:奇数` ,代码就不写了吧。。。脑洞再开 和0做与运算也是可以的`a&0==0?偶数:奇数` # 例三:找出那个唯一成对的数 # 1-1000这1000个数放在含有1001个元素的数组中,只有唯一的一个元素值重复,其它均只出现 一次。每个数组元素只能访问一次,设计一个算法,将它找出来;不用辅助存储空 间,能否设计一个算法实现? 解法一、显然已经有人提出了一个比较精彩的解法,将所有数加起来,减去`(1+2+...+1000)`的和。 这个算法已经足够完美了,相信出题者的标准答案也就是这个算法,唯一的问题是,如果数列过大,则可能会导致溢出。 解法二、异或就没有这个问题,并且性能更好。 将所有的数全部异或(1^2^…^1000^k,k为重复数),得到的结果与(1^2^3^…^1000)的结果进行异或,得到的结果就是重复数。 即`(1^2^...^1000^k)^(1^2^3^...^1000)`,由于有结合律、交换律存在,我们可以这么调整为`(1^1^2^2^...^1000^1000^k)`那结果当然就是k了,哈哈哈 # 例四:上例变形,找出出现奇数次的数 # > google面试题的变形:一个数组存放若干整数,一个数出现奇数次,其余数均出现偶数次,找出这个出现奇数次的数? `结果=a[0]^a[1]^...^a[n-1]` 因为奇数个数字连续异或之后是自己,偶数个数连续异或后为0,自己和0异或还是自己。。。真的很神奇 # 例五:再变形——找出那个唯一落单的数 # > 一个数组里除了一个数字之外,其他的数字都出现了两次。请写程序找出这个只出现一次的数字。 套路是一样的,所有元素连续求异或,得到的结果为只出现一次的数字。 # 例六:突然变难,找出数组中落单的两个数 # > 题目:一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。 ## 开脑洞 ## 先试试之前的套路:`a[1]^a[2]...^a[n] = a[x]^a[y]`,a\[x\]和a\[y\]就是这两个数,因为其他数出现偶数次,在异或过程中被自己干掉了(^\_^),但是我们得到的结果是`a[x]^a[y]`,怎么把他俩分开呢? 继续在结果上分析,既然a\[x\]和a\[y\]不同,他俩一定在某一个位(记为N)上其中一个是0,其中一个是1(读者仔细想想!),异或值在该位为1,如果找不到这样的差别,二者岂不是相同了? 既然这样,我们可以根据这个性质把数组区分为两个子数组,其中一个子数组(s1)的所有元素在N二进制位上为1,另一个子数组(s2)的所有元素在N二进制位上为0,这样s1必然包含a\[x\]和a\[y\]中的一个而s2则包含另一个且s1和s2的元素一定不同(即不会把成对的数分割),分别对两个子数组实施上面的套路(依次连续异或)就会得到两个结果,这两个结果就是最终结果。 伪代码: `xorOfResult = a[1]^a[2]...^a[n]` `N = 0` `while(true){` `if(xorOfResult & (1<<N++) == 1)` `break` `}` `/*这个得出N位为整数的第一个非0(即1)位的方法很巧妙:和1做按位与运算,如果位上为1结果为1,N求出;` `如果位上为0则结果为0,将1移动到下一位继续判断*/` `N-- // 循环最后多加了1` `s1 = new Array(),s2 = new Array()` `for i=1 to n` `if(a[i] & (1<<N) == 0)` `s1.push(a[i])` `else` `s2.push(a[i])` `define result1 = 0,result2 = 0` `for e_s1 in s1` `result1 ^= e_s1` `for e_s2 in s2` `result2 ^= e_s2` 代码还可以微调,不使用额外的数组作为存储空间: `...上面求出了N` `define result1 = 0,result2 = 0` `for i=1 to n` `if(a[i] & (1<<N) == 0)` `result1 ^= a[i]` `else` `result2 ^= a[i]` 小结 这个案例相比之前,难度有所跨越,它综合运用到了几个知识: * 异或运算 * 相同的数在某位上一定相同 * 朴素的分治,将数分为两类,再分别求解 * 移位运算 * 与运算:判断某位是否为0这也可以出个题了 # 例七: 找到连续自然数中跑丢的两个数 # > 题目为:给你1-1000个连续自然数,然后从中随机去掉两个,再打乱顺序,要求只遍历一次,求出被去掉的两个数。 使用异或:其实打乱与否没有关系,我们为这个数组添加1-1000这1000个数,问题就变成了求解一个数组中不成对的两个数,其他数都成对,即变成了上例的求解。 过程略。 # 例八: 思考题:再升级,找出落单的三个数 # > 一个数组中有三个数字a、b、c只出现一次,其他数字都出现了两次。请找出三个只出现一次的数字。 (与最前面的一题不同,前面是2个不同,现在是3个) (要求空间为O(1),所以用hash判断是否重复这种方法不管用了) 相关推导和代码可以看[这里][Link 1] # 例九: 思考题:不用判断语句,求整数的绝对值 # 一般思考:正数返回本身,负数取反+1,但这涉及到判定数是正的还是负的 提示:带符号右移31位,正数变为0,负数变为-1(1111 1111 … 1111 1111),任何数和-1做“异或”运算相当于取反……只能说这么多了 [Link 1]: https://lanqiao.coding.me/ref/TheThreeSingleNum
还没有评论,来说两句吧...