java的异或_java中的异或

java的异或_java中的异或一、异或介绍异或是一种基于二进制的位运算,用符号XOR或者^表示,其运算法则是对运算符两侧数的每一个二进制位,同值取0,异值取1。性质1、交换律2、结合律(即(a^b)^c==a^(b^c))3、对于任何数x,都有x^x=0,x^0=x4、自反性AXORBXORB=AXOR0=A二、异或使用异或运算最常见于多项式除法,不过它最重要的性质还是自反性:A^B^B…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

一、异或介绍

异或是一种基于二进制的位运算,用符号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 ^ B ^ B = A,即对给定的数A,用同样的运算因子(B)作两次异或运算后仍得到A本身。

例如,所有的程序教科书都会向初学者指出,要交换两个变量的值,必须要引入一个中间变量。但如果使用异或,就可以节约一个变量的存储空间: 设有A,B两个变量,存储的值分别为a,b,则以下三行表达式将互换他们的值 表达式 (值) :

A = A^ B

B = B ^ A

A = 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);

}

四、交换两个数的三种方法

1432840-20181117195920977-515163327.png

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中。完成交换。

参考文献: https://www.cnblogs.com/JhSonD/p/6374397.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/186084.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • mysql15免费注册激活码【最新永久激活】

    (mysql15免费注册激活码)2021最新分享一个能用的的激活码出来,希望能帮到需要激活的朋友。目前这个是能用的,但是用的人多了之后也会失效,会不定时更新的,大家持续关注此网站~IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.html…

  • .NET控件名称缩写一览表「建议收藏」

    .NET控件名称缩写一览表「建议收藏」.NET控件名称缩写一览表

  • dos命令进入d盘文件夹(windows cd到d盘)

    如何运行命令提示符,然后使用CD命令进入制定文件夹在win系统下进入命令提示符的方式是在开始的输入框中输入“cmd”,然后按“enter”进入。cd为进入的命令。具体步骤如下:步骤一:在pc端主界面中点击“开始”菜单栏,输入“cmd”,按“enter”进入命令提示符界面。步骤二:使用cd命令进入e盘。如何运行命令提示符,然后使用CD命令进入制定文件夹?使用CD命令进入指定文件?比如在桌面文…

  • C++实现二叉树层序遍历

    C++实现二叉树层序遍历层序遍历图示实现二叉树的层次遍历,要利用到队列。基本思想:1.先将根节点放到队列中2.根节点弹出队列,然后将根节点的左、右儿子入队3.弹出左儿子,放入左儿子的左右儿子4.弹出右儿子,放入右儿子的左右儿子5.重复3、4步图示过程:所用的二叉树如下队列的操作:将根节点弹出,放入左右儿子:将B节点弹出,放入左右儿子(只有右儿子):把D节点弹出,放入左右儿子:C、E、F都没有儿子节点,所以直接弹出队列即可: C++代码实现1.利用前序遍历思想输入二叉树。(前序

  • springboot引用自定义属性

    springboot引用自定义属性

  • poj3984迷宫问题_迷宫代码

    poj3984迷宫问题_迷宫代码POJ 3984 迷宫问题

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号