java异或-Java异或运算总结.pdf
异或运算的性质: 异或运算是基于⼆进制的位运算,采⽤符号XOR或者^来表⽰,运算规则是就与⼆进制,如果是同值取0、异值取1。 简单的理解就是不进位加法,例如1+1=0,0+0=0,1+0=0; 性质: 1. 交换律 可以任意交换运算因⼦,结果不变。 2. 结合律 (a^b)^c=a^(a^c) 3. 对于任何数x,都有x^x=0,x^0=x,同⾃⼰求异或运算为0,同0求异或运算结果为⾃⼰ 4. ⾃反性,A^B^B=A^0=A。这个性质可以⽤来求哪⼀个数为⼀个 ⽤法实例: 例⼀:在不引⼊第三个变量的情况下,两个变量的值(整数) //交换a、b的值 例⼆:判断奇数偶数更简单更⾼效的做法 //这个实际考的不多, 太简单 //思路:奇数的⼆进制最低为⼀定为1,偶数的⼆进制最低位⼀定为0, a^1==1?偶数:奇数 例三:找出唯⼀⼀个成对的数 题⼲: 题⼲:1-1000这1000个数放在含有1001个元素的数组中,只有唯⼀的⼀个元素值重复,其它均只出现 ⼀次。每个数组元素只能 访问⼀次,设计⼀个算法,将它找出来;不⽤辅助存储空 间,能否设计⼀个算法实现? 第⼀种解题思路:将所有的数加起来减去(1 Java中的异或运算是一种二进制位操作,用于处理整数。异或运算符用`^`表示,其运算规则是:如果两个位相同,则结果为0;如果两个位不同,则结果为1。这种运算在计算机科学中有着广泛的应用,尤其是在位操作、数据加密和优化算法中。 异或运算具有以下基本性质: 1. **交换律**:异或运算的两个操作数可以互换位置,结果保持不变,即 `a ^ b == b ^ a`。 2. **结合律**:异或运算满足结合律,即 `(a ^ b) ^ c == a ^ (b ^ c)`。 3. **恒等性**:任何数与自身异或的结果为0,即 `x ^ x == 0`;任何数与0异或的结果为该数本身,即 `x ^ 0 == x`。 4. **自反性**:一个数与另一个数异或后再与该数异或一次,结果等于原数,即 `A ^ B ^ B == A ^ 0 == A`。 这些性质使得异或运算在解决某些特定问题时特别有用。例如: - **交换两个变量的值**:无需引入额外的变量,可以通过异或操作实现两个整数变量a和b的值互换,`a = a ^ b; b = a ^ b; a = a ^ b;` - **快速判断奇偶性**:通过计算一个整数与1的异或结果,可以确定该数是否为偶数。如果结果为0,那么该数为偶数,否则为奇数。 - **查找数组中唯一的重复数**:在给定数组中,如果只有一个元素重复,其余元素各出现一次,可以通过将所有元素异或操作来找到这个重复的元素。如题干所述,所有元素异或后,重复的元素会抵消掉其他所有元素,留下重复的那个。 例如,在一个包含1到1000的数组中,有一个元素重复,其他元素各出现一次,我们可以将数组中的所有元素异或,结果即为那个重复的数。但这种方法可能导致内存溢出,因此可以先预计算`1^2^3^...^1000`,然后将所有数组元素与之异或,得到的结果与预计算值再异或一次,就可以得到重复的数。 更进一步,如果需要找出数组中仅出现一次的两个数,可以通过异或操作的自反性和位运算的特性进行处理。对所有数组元素求异或,得到的结果`total`包含了两个数异或后的结果。然后,通过找到`total`的第一个非零位`n`,将数组元素根据该位是否为1分为两组,分别对两组元素进行异或,即可得到两个只出现一次的数字。 例如,对于数组`{1, 2, 3, 3, 4, 4, 5, 6, 5, 6}`,先计算`total = a[0]^a[1]^...^a[n-1]`,然后找到`total`的第一个非零位`n`,将数组元素根据第`n`位是否为1分为两组,分别异或,得到的两个结果就是仅出现一次的数字。 Java中的异或运算因其独特的性质,常常被用来解决一些位操作问题,尤其是在资源有限或需要高效算法的场景下。理解和熟练运用异或运算,能够帮助开发者设计出更优雅和高效的代码。




















- 粉丝: 6792
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助


最新资源


