随笔06：异或的性质

r囧r小猫 2022-10-23 14:27 154阅读 0赞

转载请注明出处：http://blog.csdn.net/ns\_code/article/details/27568975

这篇文章没有代码。介绍的是纯理论的思路。  
        异或是一种基于二进制的位运算，用符号XOR或者 ^ 表示。其运算法则是对运算符两側数的每个二进制位，同值取0，异值取1。它与布尔运算的差别在于，当运算符两側均为1时，布尔运算的结果为1，异或运算的结果为0。

== 异或的性质：==

*  交换律：a^b = b^a；
 *  结合律：(ab)c = a(bc)；
 *  对于随意的a：aa=0，a0=a。a^(-1)=~a。

了解了上面这些。来看看这个，非常重要。后面的程序都要用到这个结论：

**`对于随意的a，有a^b^c^d^a^k = b^c^d^k^(a^a) = b^c^d^k^0 = b^c^d^k，也就是说。假设有多个数异或，当中有反复的数，则不管这些反复的数是否相邻。都能够依据异或的性质将其这些反复的数消去。`**

详细来说，假设反复出现了偶数次。则异或后会所有消去。假设反复出现了奇数次，则异或后会保留一个。

以下来看两道题目：

*  1、1-1000放在含有1001个元素的数组中，仅仅有唯一的一个元素值反复，其它均仅仅出现一次。每个数组元素仅仅能訪问一次，设计一个算法，将它找出来；不用辅助存储空间，是否能设计一个算法实现？

当然。这道题，能够用最直观的方法来做。将所有的数加起来，减去1+2+3+…+1000的和，得到的即是反复的那个数，该方法非常easy理解，并且效率非常高。也不须要辅助空间。唯一的不足时，假设范围不是1000。而是更大的数字，可能会发生溢出。

我们考虑用异或操作来解决该问题。

如今问题是要求反复的那个数字，我们姑且假设该数字式n吧，假设我们能想办法把1-1000中除n以外的数字所有异或两次。而数字n仅仅异或一次。就能够把1-1000中出n以外的所有数字消去，这样就仅仅剩下n了。

我们首先把所有的数字异或，记为T，能够得到例如以下：

**`T = 1^2^3^4...^n...^n...^1000 = 1^2^3...^1000（结果中不含n）`**

而后我们再让T与1-1000之间的所有数字（仅包括一个n）异或。便可得到该反复数字n。例如以下所看到的：

**`T^(a^2^3^4...^n...^1000) = T^(T^n) = 0^n = n`**

这道题到此为止。

*  2、一个数组中仅仅有一个数字出现了一次，其它的所有出现了两次，求出这个数字。

明确了上面题目的推导过程，这个就非常easy了，将数组中所有的元素所有异或，最后出现两次的元素会所有被消去，而最后会得到该仅仅出现一次的数字。

该题目相同能够该为例如以下情景，思路是一样的：数组中仅仅有一个数字出现了奇数次，其它的都出现了偶数次。

发表评论取消回复

表情：

评论列表（有 0 条评论，154人围观）

还没有评论，来说两句吧...

相关阅读

相关 Leetcode 1442. 形成两个异或相等数组的三元组数目（异或性质）

给你一个整数数组 arr 。现需要从数组中取三个下标 i、j 和 k ，其中 (0 <= i < j <= k < arr.length) 。a ...

亦凉/ 2024年05月08日 06:23/ 0 赞/ 67 阅读

相关 c语言异或(c语言异或符号)

请帮我讲解一下C语言中的异或运算首先，我们看一下异或的原理： a = 3 ^ 5; 3的二进制是0011，5的二进制是0101。异或发现两者的不同之处，所以a最终为

Myth丶恋晨/ 2023年09月26日 12:30/ 0 赞/ 80 阅读

相关二进制异或

[https://blog.csdn.net/qq\_35937273/article/details/82724247][https_blog.csdn.net_qq_359

刺骨的言语ヽ痛彻心扉/ 2023年08月17日 16:26/ 0 赞/ 130 阅读

相关 java 异或排序_Java中的异或(转)

在java程序里面的异或用法：相同输出0，不同输出1，例如： System.out.println(1^1); 输出0 System.out.println(1^2)；

忘是亡心i/ 2022年11月03日 11:24/ 0 赞/ 203 阅读

相关随笔06：异或的性质

转载请注明出处：http://blog.csdn.net/ns\_code/article/details/27568975 这篇文章没有代码

r囧r小猫/ 2022年10月23日 14:27/ 0 赞/ 155 阅读

相关 ^异或的性质和使用

^表示异或，也就是相同为0，不同为1 。其有很多性质： a ^ a = 0。 a ^ 0 = a等使用异或交换a 和 b的值。 a = 5; b

ゝ一世哀愁。/ 2022年10月04日 15:49/ 0 赞/ 368 阅读

相关异或运算符

/ ^的特点：a 异或 b 两次得到的还是 a。 / class OperatorDemo{ public static void main(S

桃扇骨/ 2022年05月22日 06:41/ 0 赞/ 230 阅读

相关 codeforces1151B题解(异或的性质)

输入n行，m列。从每一行取一个值，使他们的异或和>0，输出TAK和n个满足条件的每一行的列数，如果不能构成，输出NIE。 / Created by hao

蔚落/ 2022年02月14日 15:13/ 0 赞/ 262 阅读

相关异或的性质及运用

异或是一种基于二进制的位运算，用符号XOR或者 ^ 表示，其运算法则是对运算符两侧数的每一个二进制位，同值取0，异值取1。它与布尔运算的区别在于，当运算符两侧均为1时，布尔运算

Dear 丶/ 2022年01月06日 16:29/ 0 赞/ 284 阅读

相关异或的用途

> 正式进入高深的算法之前，我们先来学些小技巧。本章拿异或开刀，你会发现一些很有趣的东西。异或的性质异或是一种基于二进制的位运算，用符号XOR或者 ^ 表示，其运算

约定不等于承诺〃/ 2021年09月27日 05:28/ 0 赞/ 500 阅读