个人网站建设如何选服务器,域名交易网站哪个好,codeigniter 手机网站开发,哈尔滨网站推广优化公司异或是一种基于二进制的位运算#xff0c;用符号XOR或者 ^ 表示#xff0c;其运算法则是对运算符两侧数的每一个二进制位#xff0c;同值取0#xff0c;异值取1。它与布尔运算的区别在于#xff0c;当运算符两侧均为1时#xff0c;布尔运算的结果为1#xff0c;异或运算… 异或是一种基于二进制的位运算用符号XOR或者 ^ 表示其运算法则是对运算符两侧数的每一个二进制位同值取0异值取1。它与布尔运算的区别在于当运算符两侧均为1时布尔运算的结果为1异或运算的结果为0。 简单理解就是不进位加法如110,000,101。 性质 1、交换律 2、结合律即(a^b)^c a^(b^c) 3、对于任何数x都有x^x0x^0x 4、自反性 A XOR B XOR B A xor 0 A 异或运算最常见于多项式除法不过它最重要的性质还是自反性A XOR B XOR B A即对给定的数A用同样的运算因子B作两次异或运算后仍得到A本身。这是一个神奇的性质利用这个性质可以获得许多有趣的应用。 例如所有的程序教科书都会向初学者指出要交换两个变量的值必须要引入一个中间变量。但如果使用异或就可以节约一个变量的存储空间 设有A,B两个变量存储的值分别为ab则以下三行表达式将互换他们的值 表达式 值 AA XOR B (a XOR b) BB XOR A (b XOR a XOR b a) AA XOR B (a XOR b XOR a b) 类似地该运算还可以应用在加密数据传输校验等等许多领域。 运用距离 1-1000放在含有1001个元素的数组中只有唯一的一个元素值重复其它均只出现一次。每个数组元素只能访问一次设计一个算法将它找出来不用辅助存储空间能否设计一个算法实现 解法一、显然已经有人提出了一个比较精彩的解法将所有数加起来减去12...1000的和。这个算法已经足够完美了相信出题者的标准答案也就是这个算法唯一的问题是如果数列过大则可能会导致溢出。解法二、异或就没有这个问题并且性能更好。将所有的数全部异或得到的结果与1^2^3^...^1000的结果进行异或得到的结果就是重复数。但是这个算法虽然很简单但证明起来并不是一件容易的事情。这与异或运算的几个特性有关系。首先是异或运算满足交换律、结合律。所以1^2^...^n^...^n^...^1000无论这两个n出现在什么位置都可以转换成为1^2^...^1000^(n^n)的形式。其次对于任何数x都有x^x0x^0x。所以1^2^...^n^...^n^...^1000 1^2^...^1000^(n^n) 1^2^...^1000^0 1^2^...^1000即序列中除了n的所有数的异或。令1^2^...^1000序列中不包含n的结果为T则1^2^...^1000序列中包含n的结果就是T^n。T^(T^n)n。所以将所有的数全部异或得到的结果与1^2^3^...^1000的结果进行异或得到的结果就是重复数。当然有人会说12...1000的结果有高斯定律可以快速计算但实际上1^2^...^1000的结果也是有规律的算法比高斯定律还该简单的多。 google面试题的变形一个数组存放若干整数一个数出现奇数次其余数均出现偶数次找出这个出现奇数次的数 解法有很多但是最好的和上面一样就是把所有数异或最后结构就是要找的原理同上 奇数个异或是本身偶数个是00^aa异或有交换律 转载于:https://www.cnblogs.com/JSD1207ZX/p/9386255.html
