Java中异或的深入讲解

前言

异或是一种基于二进制的位运算,用符号XOR或者 ^ 表示,其运算法则是对运算符两侧数的每一个二进制位,同值取0,异值取1。

性质

1、交换律

2、结合律(即(a^b)^c == a^(b^c))

3、对于任何数x,都有x^x=0,x^0=x

4、自反性 A XOR B XOR B = A XOR 0 = A

异或运算最常见于多项式除法,不过它最重要的性质还是自反性:A XOR B XOR B = A,即对给定的数A,用同样的运算因子(B)作两次异或运算后仍得到A本身。这是一个神奇的性质,利用这个性质,可以获得许多有趣的应用。 例如,所有的程序教科书都会向初学者指出,要交换两个变量的值,必须要引入一个中间变量。但如果使用异或,就可以节约一个变量的存储空间: 设有A,B两个变量,存储的值分别为a,b,则以下三行表达式将互换他们的值 表达式 (值) :

A=A XOR B (a XOR b)
 B=B XOR A (b XOR a XOR b = a)
 A=A XOR B (a XOR b XOR a = b)

例:

int a = 10, b = 5
a = a ^ b;
b = a ^ b;
a = a ^ b;

类似地,该运算还可以应用在加密,数据传输,校验等等许多领域。

应用举例:1-1000放在含有1001个元素的数组中,只有唯一的一个元素值重复,其它均只出现一次。每个数组元素只能访问一次,设计一个算法,将它找出来;不用辅助存储空间,能否设计一个算法实现?

解法一、显然已经有人提出了一个比较精彩的解法,将所有数加起来,减去1+2+...+1000的和。这个算法已经足够完美了,相信出题者的标准答案也就是这个算法,唯一的问题是,如果数列过大,则可能会导致溢出。

解法二、异或就没有这个问题,并且性能更好。将所有的数全部异或,得到的结果与1^2^3^...^1000的结果进行异或,得到的结果就是重复数。

但是这个算法虽然很简单,但证明起来并不是一件容易的事情。这与异或运算的几个特性有关系。首先是异或运算满足交换律、结合律。

所以,1^2^...^n^...^n^...^1000,无论这两个n出现在什么位置,都可以转换成为1^2^...^1000^(n^n)的形式。
其次,对于任何数x,都有x^x=0,x^0=x。

所以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的结果进行异或,得到的结果就是重复数。

当然有人会说,1+2+...+1000的结果有高斯定律可以快速计算,但实际上1^2^...^1000的结果也是有规律的,算法比高斯定律还该简单的多。

google面试题的变形:一个数组存放若干整数,一个数出现奇数次,其余数均出现偶数次,找出这个出现奇数次的数?

public void fun() {
  int a[] = { 22, 38,38, 22,22, 4, 4, 11, 11 };
  int temp = 0;
  for (int i = 0; i < a.length; i++) {
    temp ^= a[i];
  }
  System.out.println(temp);
}

解法有很多,但是最好的和上面一样,就是把所有数异或,最后结果就是要找的,原理同上!!

************************************分割线*******************************************

这样可以实现不引人第三个变量实现交换,但是进行的计算相对第三个变量多,所以效率会低一些。

关于其他的方法还有:int a=5,b=10;
a=a+b;   //a=15,b=10
b=a-b;   //a=15,b=5
a=a-b;   //a=10,b=5

但是这样做有一个缺陷,假设它运行在vc6环境中,那么int的大小是4 Bytes,所以int变量所存放的最大值是2^31-1即2147483647,如果我们令a的值为2147483000,b的值为1000000000,那么a和b相加就越界了。

事实上,从实际的运行统计上看,我们发现要交换的两个变量,是同号的概率很大,而且,他们之间相减,越界的情况也很少,因此我们可以把上面的加减法互换,这样使得程序出错的概率减少:

int a=5,b=10;
a -= b;   //a=-5,b=10
b += a;   //b=5,a=-5
a = b - a;   //a=10,b=5

通过以上运算,a和b中的值就进行了交换。表面上看起来很简单,但是不容易想到,尤其是在习惯引入第三变量的算法之后。
它的原理是:把a、b看做数轴上的点,围绕两点间的距离来进行计算。

具体过程:第一句“a-=b”求出ab两点的距离,并且将其保存在a中;第二句“b+=a”求出a到原点的距离(b到原点的距离与ab两点距离之差),并且将其保存在b中;第三句“a+=b”求出b到原点的距离(a到原点距离与ab两点距离之和),并且将其保存在a中。完成交换。

下面顺便介绍交换两个数 的三种方法:

总结

以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,谢谢大家对我们的支持。

(0)

相关推荐

  • java中的异或问题代码解析

    java的位运算符中有一个叫异或的运算符,用符号(^)表示,其运算规则是:两个操作数的位中,相同则结果为0,不同则结果为1.下面看一个例子: public class TestXOR{ public static void main(String[] args){ int i = 15, j = 2; System.out.println("i ^ j = " + (i ^ j)); } } 运行结果是:i^j=13. 分析上面程序,i=15转成二进制是1111,j=2转成二进制是00

  • Java异或技操作给任意的文件加密原理及使用详解

    异或简单介绍:异或是一种基于二进制的位运算,用符号XOR或者 ^ 表示,其运算法则是对运算符两侧数的每一个二进制位,同值取0,异值取1. 简单理解就是不进位加法,如1+1=0,,0+0=0,1+0=1. 需求描述 在信息化时代对数据进行加密是一个很重要的主题,在做项目的过程中,我也实现了一个比较复杂的加密算法,但是由于涉及到的技术是保密的,所以在这里我实现一个比较简单的版本,利用文件的输入输出流和异或操作进行任意文件的加密,关于解密算法,很简单,自己思考下就能解决. 数学原理 该加密算法利用的是

  • java异或加密算法

    简单异或密码(simple XOR cipher)是密码学中中一种简单的加密算法. 异或运算:m^n^n = m; 利用异或运算的特点,可以对数据进行简单的加密和解密. 复制代码 代码如下: /** * 简单异或加密解密算法 * @param str 要加密的字符串 * @return */private static String encode2(String str) { int code = 112; // 密钥 char[] charArray = str.toCharArray(); 

  • Java中使用异或运算符实现加密字符串

    通过异或运算符号与一个指定的值进行异或运算,从而改变字符串每个字符的值,这样就可以得到加密后的字符串. import java.util.Scanner; public class Encypt { public static void main(String args[]){ Scanner scan = new Scanner(System.in); System.out.println("请输入一个英文字符串或解密字符串:"); String password = scan.ne

  • Java中使用异或语句实现两个变量的互换

    一般实现两个变量之间的互换要用第三个变量,这样做可以,但创建新变量,增加了系统开销.如果要交换的变量时两个整数型变量,可以用更高效的方法.例如:^(异或)操作,举例如下: import java.util.Scanner; public class VariableExchange { public static void main(String args[]){ Scanner scan = new Scanner(System.in); System.out.println("请输入第一个整

  • Java中位运算(移位、位与、或、异或、非) 的简单实例

    复制代码 代码如下: public class Test {     public static void main(String[] args) {         // 1.左移( << )         // 0000 0000 0000 0000 0000 0000 0000 0101 然后左移2位后,低位补0://         // 0000 0000 0000 0000 0000 0000 0001 0100 换算成10进制为20         System.out.pri

  • java实现两个文件的异或运算

    本文实例为大家分享了java实现两个文件的异或运算的具体代码,供大家参考,具体内容如下 以下代码是将两个大小相同的文件异或之后生成一个新的文件,具体思想是用FileInputStream方法读取文件,以字节为单位对两个文件进行异或运算,然后用FileOutputStream方法输出文件,具体代码如下: import java.io.File; import java.io.FileInputStream; import java.io.FileOutputStream; import java.

  • Java编程实现对十六进制字符串异或运算代码示例

    前言:好久没有写博客,最近一年感觉真是好忙,各种做不完的工作.相信很多上班族都会有这种感觉.最近对NFC进行写卡操作,需要计算一个校验位.一般情况下,校验位多数是由前几个字节进行异或运算所得. 现在我就先说一下我使用的场景: 把一个16字节的数据写到CPU卡(如交通卡)里面,最后一字节是校验码---前十五字节异或. 我开始从网上找了一些别人写的算法发现计算后结果不对,或者就是写的太复杂了,于是自己就写了一个,感觉也比较简单,现在分享给大家,希望一起交流一下. 第一节:什么是异或运算(主要摘自百度

  • java使用异或实现变量互换和异或加密解密示例

    复制代码 代码如下: import java.util.Scanner; public class VariableExchange {    public static void main(String[] args){        System.out.println("请输入变量A的值");        Scanner scanner=new Scanner(System.in);        long A=scanner.nextLong();        System

  • Java使用异或运算实现简单的加密解密算法实例代码

    Java简单的加密解密算法,使用异或运算 实例1: package cn.std.util; import java.nio.charset.Charset; public class DeEnCode { private static final String key0 = "FECOI()*&<MNCXZPKL"; private static final Charset charset = Charset.forName("UTF-8"); pr

随机推荐