动力节点旗下在线教育品牌  |  咨询热线:400-8080-105 学Java全栈,上蛙课网
首页 > 文章

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

07-27 16:55 230浏览
举报 T字号
  • 大字
  • 中字
  • 小字

  Java异或运算是基于二进制的位运算,应用于逻辑运算,采用符号XOR或者^来表示,运算规则是就与二进制,如果是同值取0、异值取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。这个性质可以用来求解哪一个数为同一个数。

用法实例:

例一:在不引入第三个变量的情况下,两个变量的值(整数)

//交换a、b的值

a=a^b

b=a^b

a=a^b

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

//思路:奇数的二进制最低为一定为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,4,5,6,5,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,arr2=0;

        for (int i = 0; i

            arr1^=num1.get(i);

 

        }

        for (int i = 0; i

            arr2^=num2.get(i);

 

        }

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

 

    }

}

例六:找连续自然数中跑丢的两个数

题目为:给你1-1000个连续自然数,然后从中随机去掉两个,再打乱顺序,要求只遍历一次,求出被去掉的两个数。

思路和例题6一样了,先用(1^2^3...^1000)与去掉的异或运算,之后就可以用例题6计算了。

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

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

寻找数组中只出现一次的三个数

lanqiao.coding.me

例八:不用判断语句,求整数的绝对值

思路:正数返回本身,负数取反+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代码肯定也是漏洞百出了。

0人推荐
共同学习,写下你的评论
0条评论
天行九歌
程序员天行九歌

6篇文章贡献29402字

作者相关文章更多>

推荐相关文章更多>

Java数据结构

HelloWorld10-31 08:24

浅谈MySQL中SQL优化的常用方法

军哥08-12 23:29

五分钟读懂UML类图

江湖人称小李白12-10 10:41

MyBatis开发框架的四大核心

IT逐梦者08-17 21:43

一次搞定continue,break和return

HelloWorld11-06 11:19

发评论

举报

0/150

取消