异或运算的基本介绍以及使用技巧,剖析常见的异或题目

这篇具有很好参考价值的文章主要介绍了异或运算的基本介绍以及使用技巧,剖析常见的异或题目。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、异或运算的基本介绍

异或运算,符号为‘^’,直接对底层二进制串进行运算,比算术运算快得多,规则为:相同为0,不同为1。
异或运算,算法,算法,java,开发语言

二、异或运算的性质

假设N为任意实数
性质1:0 ^ N = N
性质2:N ^ N = 0
性质3:异或运算满足交换律与结合律
重点:我们可以将异或运算理解为二进制的无进位相加!也就是说,当两个数异或的时候,如果某一位同为1,则该位为0并且不向前进位。

三、异或运算的经典题目

1.题目1

题名:如何不使用额外的变量交换两个数字
需求:给定一个int类型的a = 1,与一个int类型的b = 2,请交换这两个数
思路分析:
我们可以利用异或的性质来完成这个题目。

  1. a = a ^ b :此时a = a ^ b, b = b
  2. b = a ^ b :此时a = a ^ b, b = a ^ b ^ b = a
  3. a = a ^ b :此时a = a ^ b ^ a = b, b = a
    最后两个数就交换过来了
  • 注意:如果变量a与变量b是指向的同一块内存空间,那么就不能使用这种方法交换,因为同一个内存空间的话,一次异或就相当于这块空间自己与自己异或,结果为0,此时0结果无法改变了。
    代码:
public class no_02_题目1如何不用额外变量交换两个数 {
    public static void main(String[] args) {
        //测试一把
        int a = 1;
        int b = 2;
        System.out.println("交换前:");
        System.out.println("a = " + a);//1
        System.out.println("b = " + b);//2
        //异或交换
        a = a ^ b;
        b = a ^ b;
        a = a ^ b;
        System.out.println("交换后:");
        System.out.println("a = " + a);//2
        System.out.println("b = " + b);//1

        //测试对同一块空间异或会发生什么
        int[] arr = {1,2};
        //异或前
        System.out.println(arr[0]);//1
        arr[0] = arr[0] ^ arr[0];
        arr[0] = arr[0] ^ arr[0];
        arr[0] = arr[0] ^ arr[0];
        //异或后
        System.out.println(arr[0]);//0
    }
}

运行结果:
异或运算,算法,算法,java,开发语言

2.题目2

题目:一个数组中有一种数出现了奇数次,其他的数都出现了偶数次,怎么找到并打印这个出现了奇数次的数?
思路分析:
1)准备一个变量 eor = 0
2)让这个变量eor 和 数组arr中所有的数字都进行异或运算
3)最终得到的eor就是我们要找的出现了奇数次的数

  • 解释:
    利用异或性质,因为出现了偶数次的数异或为0,出现了奇数次的数异或为该奇数本身,让0与所有数异或最后0就会变为那个奇数
    代码:
public class no_02_题目2 {
    public static void main(String[] args) {
        //测试一把
        int[] arr = {1,1,1,2,2,2,2,3,3,3,3,4,4};//1出现了3次
        int eor = 0;
        //使用了加强for循环
        for (int i:arr)
            eor ^= i;//eor与arr中所有数进行异或
        System.out.println("出现了奇数次的数为:" + eor);//1
    }
}

运行结果:
异或运算,算法,算法,java,开发语言

3.题目3

题目3讲解的内容与异或无关,但是也很重要,是一种经常使用的操作。
题目:提取一个数的二进制串最右侧的1
思路分析:
一步到位:int righrOne = num & (~num + 1)

  • 解释:比如num = 1000111010 1000
    1.先取反
    num = 0111000101 0111
    2.加1
    num = 0111000101 1000
    3.和原来的num按位与&(只有都是1才是1,其余为0)
    1000111010 1000
    0111000101 1000
    结果是:0000000000 1000 这样就得到了最右边的1
    代码:
public class no_03_题目3提取最右侧的1 {
    public static void main(String[] args) {
        //测试一把
        int num = 100;//二进制:101 0100
        int rightOne = num & (~num + 1);
        System.out.println(num + "二进制最右侧的1转化为10进制是:" + rightOne);//4 :二进制000 0100
    }
}

运行结果:
异或运算,算法,算法,java,开发语言

4.题目4

题目:一个数组中有两种数出现了奇数次,其他数都出现了偶数次,怎么找到并打印这两种出现了奇数次的数?假设a与b是要找的这两个数。
思路分析:

  • 1)首先让变量eor与数组所有数异或一次,eor就变为了a异或b
    eor = a ^ b
    注意:(a != b),所以eor的二进制位一定有一位是1
  • 2)提取出eor二进制最右侧的1
    rightOne = eor & (~eor + 1)
  • 3)准备新的变量onlyOne,让数组中所有在rightOne位上是1的数与onlyOne异或。只要和rightOne进行按位与,结果不是0,则该数在rightOne位上是1
int onlyOne = 0;
for(int i = 0;i < arr.length;i++)
   if(rightOne & arr[i] != 0)
         onlyOne ^= arr[i];
  • 4)此时得到的onlyOne就是a或者b的其中一个

    解释:因为a与b在rightOne这个二进制为上一定是一个0,一个1,所以我们可以将数组arr中的数分为两部分,一部分是rightnOne位上是1的数,一部分是0的数,这样就将a与b区分开,单独让onlyOne与异或上其中一部分的数,就可以得到这个出现了奇数次的数,原理与题目2一模一样。

  • 5)再让onlyOne与eor异或得到另一个数
    图解:
    异或运算,算法,算法,java,开发语言
    代码:

public class no_04_题目4 {
    public static void main(String[] args) {
        //注意:因为通过eor最右侧的1为特征,a和b在此位上必不相同,故可以用这位来划分区间
        int eor  = 0;
        int[] arr = {1,1,1,2,2,2,4,4,5,5,5,5,6,6,8,8,};
        //1.数组所有数与其异或一次
        for (int i:arr)
            eor ^= i;//eor = a ^ b;
        //2.提取eor最右侧的1【也就是a与b的划分位】
        int rightOne = eor & (~eor + 1);
        //3.准备变量onlyOne与数组中在rightOne位上是1的异或,得到a与b其中一个
        int onlyOne = 0;
        for (int i:arr)
            if ((rightOne & i) != 0)
                onlyOne ^= i;
        //4.onlyOne 就是 其中一个,onlyOne ^ eor是另一个
        System.out.println(onlyOne + "   " + (onlyOne ^ eor));
    }
}

运行结果:
异或运算,算法,算法,java,开发语言

5.题目5

题目:给你一个整数,提取其中二进制位上为1的个数
思路分析:

  • 1)获取最右位上的1
    rightOne = num & (~num + 1)
  • 2)抹去最右位的1,同时计数器记数,重复步骤1,直到num = 0
    num = num ^ rightOne;//抹去最右位的1
    代码:
public class no_05_题目5 {
    public static void main(String[] args) {
        int count = 0;//记数
        int num = 25;//0000 1101
        while(num != 0){
            int rightOne = num & (~num + 1);//获取最右位的1
            count++;//计数器
            num = num ^ rightOne;//抹去最右位的1
        }
        System.out.println("25二进制上1的个数为:" + count);//3
    }
}

运行结果:
异或运算,算法,算法,java,开发语言

四、异或运算小结

1.简便记忆异或:无进位相加
2.异或性质牢记
3.异或的简单操作要会使用
4.异或交换两个数,这两个数不能指向同一块内存空间,否则出错。文章来源地址https://www.toymoban.com/news/detail-716807.html

到了这里,关于异或运算的基本介绍以及使用技巧,剖析常见的异或题目的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【unity小技巧】委托(Delegate)的基础使用和介绍

    在Unity中,委托( Delegate )是一种用于处理方法回调的特殊类型。它允许您将方法作为参数传递给其他方法,并在需要时调用这些方法。 委托在游戏开发中非常有用࿰

    2024年02月15日
    浏览(45)
  • 微服务服务间调用组件Feign使用介绍、原理、优化技巧

    Feign是一个声明式的Web Service客户端。它让微服务之间的调用变得更简单。Feign具有可插拔式的注解支持,包括Feign 注解和JAX-RS注解。Feign还支持可插拔的编码器和解码器。Spring Cloud增加了对Spring MVC注解的支持,并且也支持Spring WebFlux。 Feign可以与Eureka和Ribbon组合使用以支持负载均

    2024年02月06日
    浏览(74)
  • K8S中Deployment控制器的概念、原理解读以及使用技巧

    Deployment官方文档: https://kubernetes.io/docs/concepts/workloads/controllers/deployment/ Deployment是kubernetes中最常用的资源对象,为ReplicaSet和Pod的创建提供了一种声明式的定义方法, 在Deployment对象中描述一个期望的状态,Deployment控制器就会按照一定的控制速率把实际状态改成期望状态,

    2024年02月21日
    浏览(46)
  • 【一些随笔】浅析 Linux和Windows:系统介绍、操作差异与使用技巧解析

    Linux和Windows系统的操作差异; Linux系统介绍、系统监控和优化技巧、Shell脚本编程技巧、一些命令使用技巧; Windows系统介绍、优化和加速技巧、一些在Windows系统下常用的快捷键; 在使用Linux和Windows时,有一些事情可能在Linux上较为顺理成章,而在Windows上可能令人费解。比如

    2024年02月13日
    浏览(45)
  • 位运算(按位与、按位或、异或、取反)以及原码、反码、补码

    目录 位运算 按位与运算符 [ ] 按位或运算符 [ | ] 异或运算符 [ ^ ] 取反运算符 [ ~ ] 移位操作 一些面试常考的位操作运算 获取二进制中最右边的1 计算机原码、反码、补码 机器数 “三码”之间的转换 计算机中为啥要用补码呢? 真数 原码 反码 补码 有了原码为什么要使用反码

    2024年02月02日
    浏览(48)
  • 【SQL开发实战技巧】系列(三十):数仓报表场景☞树形(分层)查询如何排序?以及如何在树形查询中正确的使用where条件

    【SQL开发实战技巧】系列(一):关于SQL不得不说的那些事 【SQL开发实战技巧】系列(二):简单单表查询 【SQL开发实战技巧】系列(三):SQL排序的那些事 【SQL开发实战技巧】系列(四):从执行计划讨论UNION ALL与空字符串UNION与OR的使用注意事项 【SQL开发实战技巧】系列

    2023年04月09日
    浏览(63)
  • Excel 使用技巧集锦—163种技巧

    目录 一、基本方法7 1.快速选中全部工作表7 2.快速启动E 7 XCEL 3.快速删除选定区域数据 8 4.给单元格重新命名8 5.在E 中选择整个单元格范围9 XCEL 6.快速移动/复制单元格9 7.快速修改单元格式次序 9 8.彻底清除单元格内容10 9.选择单元格10 10. 为工作表命名11 11. 一次性打开多个工作

    2024年02月03日
    浏览(49)
  • IDEA使用技巧

    目录结构: bin:容器,执行文件和启动参数等 这里以我的电脑系统(64 位 windows7, 16G 内存)为例,说明一下如何调整 VM 配置文件: 1、大家根据电脑系统的位数,选择 32 位的 VM 配置文件或者 64 位的 VM 配置文件 2、32 位操作系统内存不会超过 4G,所以没有多大空间可以调整,

    2024年02月07日
    浏览(42)
  • IDEA 使用技巧

    除了一些在Linux上用vim开发的大佬,idea算是很友好的集成开发工具了,功能全面,使用也很广泛。 记录一下我的 IDEA 使用技巧,以后想到什么会继续更新这个 我主要用IDEA开发java,不知道idea对其他语言是否也有这些支持,所以感兴趣的可以看一下 sout 快速生成Java打印语句

    2024年02月08日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包