首页 > 图灵资讯 > 技术篇>正文

实例教你快速掌握Java异或运算

2023-04-02 17:46:46

Java异或运算它是基于二进制的位置运算,用于逻辑运算,使用符号XOR或^表示操作规则与二进制相同、异值取1。简而言之,不进位加法,如1+1=0、0+0=0、1+0=1;

要彻底掌握java中的异或运算必须理解异或运算的基本性质,这与数学中的加减乘除法相似。

交换法:可任意交换运算因素,结果不变。

结合律:(a^b)^c=a^(a^c)

对于任何数x,都有x^x=0,x^0=x,与自己求异或计算为0,与0求异或计算结果为自己

自反性,A^B^B=A^0=A。这种性质可以用来解释哪个数字是相同的数字。

用法实例:

例1:两个变量的值(整数),不引入第三个变量

//交换a、b的值

a=a^b

b=a^b

a=a^b

例2:判断奇数偶数更简单、更高效的做法

//思路:奇数二进制最低为1,偶数二进制最低为0,

a^1==1偶数:奇数

例三:找出唯一成对的数字

题干:1-1000这1000个数字放在含有1001个元素的数组中,只有一个元素值重复,其他只出现 一次。每个数组元素只能访问一次,设计算法并找到它;无需辅助存储空间 间,能否设计算法实现?

第一个解决问题的想法是把所有的数字加起来减去(1+2+……+1000)。但这可能导致内存溢出。

第二种想法:将所有的值异或计算,然后与结果相结合(1^2^3……^1000)异或运算

结果相当于(1^1^2^2……1000^1000^k)最终的结果是k

例四:找出唯一一个落单的数字(即只出现一次的数字)

结果=a[0]^a[1]^...^a[n-1]

例五:(难度增加)找出数组中的两个数字。

题目:除了两个数字,一个整形数组中的其他数字都出现了两次。请写一个程序,找出这两个数字只出现一次。所需的时间复杂性是O(n),空间复杂度为O(1)。

package test.nowcoder;

import java.util.ArrayList;

import java.util.List;

/**

* @Autre beyond

* @Data 2019/10/19

* 与以前相比,这种情况有所跨越,它综合运用了几种知识:

*

* 异或运算

* 在某个位置上,相同的数字必须相同

* 简单的分治分为两类,然后分别求解

* 移位运算

* 还有运算:判断一个人是否为0也可以出问题

*

*/

public class TowNumOdd {

public static void main(String[] args) {

int [] arr={1,2,3,3,4,5,6,6;

///先求总

int n=0;

int temp=0;

for (int i = 0; i

temp^=arr[i];

}

while (true){

if ((temp&(1<

break;

}

}

/*得出N位为整数的第一个非0(即1)位的方法非常巧妙:和1做按位和操作,如果位上为1,结果为1,N得出;

如果位上为0结果为0,将1移动到下一个继续判断*/

// 最后,循环增加了1

n--;

List num1=new ArrayList<>();

List num2=new ArrayList<>();

for (int i = 0; i

if ((arr[i]&(1<

num1.add(arr[i]);

}else {

num2.add(arr[i]);

}

}

int arr1=0,ar2=0;

for (int i = 0; i

ar1^=num1.get(i);

}

for (int i = 0; i

ar2^=num2.get(i);

}

System.out.println(arr1+"+"+arr2);

}

}

例6:在连续的自然数中找到两个丢失的数字

题目是:给你1-1000个连续自然数,然后随机删除两个,然后打乱顺序,只要求一次,找出两个被删除的数字。

思路和例题6.先用(1^2^3)...^1000)可以用例题6计算和删除的异或操作。

例题七:(再次升级)找到落单的三个数字

一个数组中有三个数字a、b、c只出现一次,其他数字出现两次。请找出三个只出现一次的数字。

三个数字只出现在搜索数组中一次

lanqiao.coding.me

例8:不需要判断句子,要求整数的绝对值

思路:正数回归本身,负数取反+1.但这涉及到判断数是正还是负

提示:带符号右移31位,正数为0,负数为-1(1111 1111 … 1111 1111),任何数字和-1“异或”计算相当于取反……只能说这么多

public static void main(String[] args) {

int number;

Scanner in = new Scanner(System.in);

number = in.nextInt();

/*

* >> 右移,高补符号位

* >>> 无符号右移,高补0

* ^ 相同为0,不同为1

*/

System.out.println(number + "绝对值为:" + ((number^(number>>31))+(number>>31)));

}

Java异或操作作为java语法中最基本的操作很容易掌握。但我们不能轻视它,因为细节注定要成败。看微知道,如果基本的不同或操作可能会出错,那么整个java代码肯定是漏洞百出。

上一篇 10道JavaWeb高级面试题助你通过面试(附答案)
下一篇 Git五大高级功能及指令

文章素材均来源于网络,如有侵权,请联系管理员删除。