熟练理解和掌握位操作，在有些情况下能使程序的效率提高不少，当然代码的可读性就降低
了，维护也比较困难。相比于与操作(&),或操作(|)，异或操作(^)显得更难以理解，甚至看
不出它有什么妙用。下面列举一些用到异或操作的问题，或许能从中学到一些新的东西。
-
不使用中间变量，交换两个数的值
//version 1 void swap(int &a,int &b){ a ^= b; b ^= a; a ^= b; } //version 2 void swap(int &a,int &b){ a -= b; b += a; a = b-a; } /*注意这两个版本都有个bug，当a，b指向同一个对象时，会变成0。而且有文章指出，版本 1位操作未必比使用中间变量的性能好，再考虑到可读性，那这样的代码就更不推荐了。 姑且就当作一种娱乐吧。 */ -
有一组数字,每个数字都不相同，放在大小为N-1的数组里，数字的范围是1-N，找出丢失
的那个数。只能申请少于O(N)的常数空间，时间复杂度O(n)。如果丢失两个数呢？
/*容易想到的O(n)算法是将所有的数相加，然后用N(N+1)/2去减，得到的差就是丢失的那个 数。但问题在于所有的数之和可能会溢出。还有人说用 sum(array[i]-i),实际上这也没 有解决可能的溢出问题。 异或可以解决这个问题。将所有的数array[i]异或得到k，k再与1到N所有的数异或得到 k',则k'就是丢失的那个数a。 如果丢失两个数，同样用异或的方法。假设丢失的是a,b,则 k' = a^b,k'获得方法如上。 定义lowbit(i)函数,返回i的二进制表示中不为0的最低位，则a，b在lowbit(k')位上肯定 是不同的。将原数组array[1..N-1]中lowbit(k')位为1的数异或得到k'',再用k''与1-N中 lowbit(k')位为1的数异或得到k''',则k'''为a,b其中的一个，再用k''' ^ k'得到另一个。 */ //查找唯一丢失的数 //array 长度为N-1，值范围为1-N，数组中每个数都不相同 int findmiss(int *array,int N){ int a; // result int i; a = 0; for(i=0;i<N-1;i++) a ^= array[i]; for(i=1;i<=N;i++) a ^= i; return a; } //lowbit 的实现 int lowbit(int i){ return i & -i; } //查找丢失的两个数 //array 长度为N-2，值范围为1-N，数组中每个数都不相同 //a,b为丢失的数 void findmiss2(int *array,int N,int *a,int *b){ int i,k,lb; k = 0; *a = 0,*b = 0; for(i=0;i<N-2;i++) k ^= array[i]; /* after this recurse, k=a^b */ for(i=1;i<=N;i++) k ^= i; lb = lowbit(k); for(i=0;i<N-2;i++){ if(array[i] & lb != 0) *a ^= array[i]; else *b ^= array[i]; } for(i=1;i<=N;i++){ if(i & lb != 0) *a ^= i; else *b ^= i; } return ; } -
n个数中有且仅有一个数出现了奇数次（其他数都出现了偶数次），如果用线性时间常数
空间找出这个数？如果是两个数出现了奇数次呢？如果是三个数呢？或者是k个数？
/*如果稍微想一想，就会发现这题与题目2有很多相似之处。所以下面的解法也很类似。 第一问：有且仅有一个数出现奇数次，对数组n个数从头到尾异或一遍，得到的值即为要 求的那个数。 第二问：如果有两个数出现了奇数次。同题目2，先异或所有元素得到k，取lowbit(k), 按照lowbit(k)将原数组分为两组，对这两组分别求异或，就得到要求的两个数。 第三问: 如果是三个数。这一问就很难了，即使知道应该从异或这个角度去考虑，也很难 想出好方法。当然，总有牛人会想出好方法，关键是找出第一个来，然后借助第二问结论 求另外两个。为了不影响意思的理解，转载原文如下: // Let s = a ^ b ^ c. We know that s not in (a, b, c), // since if s == a, say, then b ^ c == 0 and b == c. // Let f(x) be the lowest bit where x differs from s. // The algorithm computes flips = f(a) ^ f(b) ^ f(c), // since the numbers appearing an even number of times cancel. // The variable flips has parity 1, so it is non-zero, // and lowbit(flips) is a bit where one or three of a, b, c // differ from s. It can't be three(这个需要仔细想想), however, so the final // exclusive-or includes exactly one of a, b, c. 第四问：如果是k个数。从第3问我们可以发现，用类似的方法总可以找出第一个来，然 后将问题转化为k-1规模的，则可以递归解决。复杂度为O(k^2*n). */ // get lowest different bit int lowbit(int x){ return x & ~(x - 1); } // Given an array of n integers, such that each number // in the array appears exactly twice, except for two // numbers (say a and b) which appear exactly once. // // In O(n) time and O(1) space find a and b. // e.g. // { 2 3 3 2 4 6 4 7 8 8 } ---> a/b = { 6 7} void Find2(int seq[], int n, int& a, int& b) { ////XOR int xors = 0; for(int i = 0; i < n; i++) xors ^= seq[i]; ////get different bit int diff = lowbit(xors); //// a = 0; b = 0; for(int i = 0; i < n; i++){ if(diff & seq[i]) a ^= seq[i]; else b ^= seq[i]; } } // Given an array of n integers, such that each number // in the array appears exactly twice, except for three // numbers (say a, b and c) which appear exactly once. // // In O(n) time and O(1) space find a,b and c. // e.g. // { 2 3 3 2 4 6 4 7 8 8 1 } ---> a/b = { 6 7 1} // Let s = a ^ b ^ c. We know that s not in (a, b, c), // since if s == a, say, then b ^ c == 0 and b == c. // Let f(x) be the lowest bit where x differs from s. // The algorithm computes flips = f(a) ^ f(b) ^ f(c), // since the numbers appearing an even number of times cancel. // The variable flips has parity 1, so it is non-zero, // and lowbit(flips) is a bit where one or three of a, b, c // differ from s. It can't be three, however, so the final // exclusive-or includes exactly one of a, b, c. void Find3(int seq[], int n, int& a, int& b, int& c) { ////XOR int xors = 0; for(int i = 0; i < n; i++) xors ^= seq[i]; //// int flips = 0; for(int i = 0; i < n; i++) flips ^= lowbit(xors ^ seq[i]); flips = lowbit(flips); ////get one of three a = 0; for(int i = 0; i < n; i++){ if(lowbit(seq[i] ^ xors) == flips) a ^= seq[i]; } ////swap a with the last element of seq for(int i = 0; i < n; i++){ if(a == seq[i]){ int temp = seq[i]; seq[i] = seq[n - 1]; seq[n - 1] = temp; } } ////call Find2() to get b and c Find2(seq, n - 1, b, c); } -
n个数中只有一个数出现了一次，其他的数出现了3次，如何用O(n)的时间复杂度，常数空
间的算法找出这个数？如果这个数出现两次呢？
/*考虑3进制。利用3进制的异或： 1 xor 0 = 1 1 xor 1 = 2 1 xor 2 = 0 2 xor 0 = 2 2 xor 2 = 1 0 xor 0 = 0 详见参考资料[4] */
-
nim游戏.有若干堆石子，每次可以选择一堆石子，从这堆石子中拿走任意数量的石
子，也就是至少拿走一个，最多把这堆石子全部拿走，两人轮流取，谁取走最后一个石子
谁就赢.问是否先手必胜。
假设有n堆石子，数量分别为a1,a2,a3...an，那么如果石子的异或和不是0， 那么先手必 胜也就是a1^a2^...^an != 0,那么先手必胜。看起来很神奇吧，感觉很复杂的游戏居然用 异或就给解决了。是不是觉得自己很笨，怎么没有想到？没啥关系，早在16世纪，nim游 戏就已经提出来了，但是到了1901年才被哈佛的一个教授解决，说明这世上跟我一样笨的 人还是很多的。详细的讨论可以看 "http://en.wikipedia.org/wiki/Nim" .那先手要怎么走呢（想想怎么使异或变为0）？
没有评论:
发表评论