位运算相关算法

devtools/2024/11/7 15:05:43/

一、异或运算介绍

1、性质介绍

异或运算(XOR,Exclusive OR)是一种位运算符。对于两个位进行异或操作,当且仅当这两个位不同时,结果为 1;如果相同,则结果为 0。

A

B

A^B
000
01

1

101
110
  • 任何数与自身异或结果为 0。
  • 任何数与 0 异或结果为自身。
  • 交换性: a^b=b^a。
  • 结合性: (a^b)^c=a^(b^c)。

2、结论

由于上面我们提到了异或运算是满足交换律结合律的,所以异或运算就有以下特性:

对于 a, b, c 三个变量相异或,无论异或的顺序是什么,结果都是相同的。

a ^ b ^ c = a ^ c ^ b = b ^ c ^ a = b ^ a ^ c = c ^ a ^ b = c ^ b ^ a

二、位运算的应用

1、不用中间变量交换两个数的值

1)介绍

	int a = 3;int b = 5;System.out.println("Before swap:\n" + "a = " + a + "\nb = " + b);a = a ^ b;b = a ^ b;a = a ^ b;System.out.println("After swap:\n" + "a = " + a + "\nb = " + b);

运行结果:

2)具体原理图解

3)补充 

这样交换只能交换两个不同位置的变量,如果对同一个变量交换,会把这个变量的值变成 0。

所以需要添加一个条件,如果是同一个元素,就不进行交换。

	public static void swap(int[] arr, int i , int j) {if(arr[i] != arr[j]) {arr[i] = arr[i] ^ arr[j];arr[j] = arr[i] ^ arr[j];arr[i] = arr[i] ^ arr[j];}}

2、找出只出现一次的元素

1)介绍

在一个数组中,其他元素都出现偶数次,只有一个元素出现奇数次,可以用异或找出它。

	public static int findOddTimes(int[] arr) {int ans = 0;for(int i : arr) {ans ^= i;}return ans;}

运行结果:

2)原理图解

3、提取二进制最低有效位的1(最右侧的1)

1)介绍

在之前的文章《Java——二进制原码、反码和补码_原码反码补码-CSDN博客》中有提到过,求一个数的相反数可以使用取反加一的方法,对于变量 a,其相反数为 -a,-a = ~a + 1。

2)详细原理图解

4、求出两个出现奇数次的数

1)介绍

输入数据为一个数组,数组中有两个不同的数 a 和 b 分别出现了奇数次,其他的数都是出现了偶数次。求出这两个不同的数。

首先我们先将数组中的所有数异或起来,然后这时的结果就是这两个不同的数的异或,也就是 a ^ b 的结果。由于这两个数是不同的,所以结果一定不为零,也就是说 a ^ b != 0。所以说这个结果的二进制中一定有某一位是 1,我们就可以通过上面给出的提取最右边的 1 的方法,将最右边的 1 提取出来。然后通过这个 1,我们就可以分辨 a 和 b,因为结果的这一位为 1,所以 a 和 b 的这一位必然不同。

然后我们再将这一数组的所有数分组异或起来,使用上面提取出的最右位置的 1 来分组,这样就可以将 a 和 b 分在不同组中,对于其他数,相同的数一定分在同一组,异或的结果就是 0,所以其他的数是没有什么影响的。

简化一下就是以下步骤:

  1. 异或运算:先对数组中所有数字进行异或,结果就是目标的两个数的异或值。

  2. 区分两数:找到异或结果中任意为1的位置,用于区分这两个数。这可以通过 xor & (-xor) 来实现,提取出最低有效位的 1。

  3. 分组异或:根据该位是否为1,将数组分成两组,然后分别对两组进行异或,这样每组会得到一个目标数。

2)代码

	public static void findTwoOddTimesNums(int[] arr) {int xor = 0;for (int i : arr) {xor ^= i;}int diff = xor & (-xor);int a = 0;int b = 0;for (int i : arr) {if ((i & diff) == 0) {a ^= i;} else {b ^= i;}}System.out.println("Two nums: " + a + ", " + b);}

运行结果:

上面的代码也可以改成下面这样:

    public static void findTwoOddTimesNums(int[] arr) {int xor = 0;for (int i : arr) {xor ^= i;}int diff = xor & (-xor);int a = 0;for(int i : arr) {if((i & diff) != 0) {a ^= i;}}System.out.println("Two nums: " + a + ", " + (xor ^ a));//这里求出了其中一个数a,由于xor是a ^ b,所以xor ^ a就得到了b}

得到的结果是类似的:

5、找到出现K次的数

1)介绍

输入一个数组,数组中有一个数是出现了K次,其他数都出现了M次,M>1,K<M,找到这个出现了K次的数。

我们可以使用一个数组bitCount统计所有数字在每个位上1的出现次数。

然后就是遍历bitCount数组,如果某一位的计数不是M倍数,就可以证明出现K次的数的这一位一定为1,反之,某一位的计数是M的倍数,则出现K次的数的这一位是0。(能够这样判断的前提是题目中的限制条件,也就是M>1,M>K,而且出现K次的数只有一个,所以说最终某位计数可能是K + M*n,也可能是M*n,由于K<M,显然K + M*n不是M的倍数,而M*n是M的倍数)

然后就可以将出现K次的数的是1的位组合起来,最终得到结果。

  1. 位计数:使用一个大小为32的数组bitCount来统计数组中所有数字在每个位上1的出现次数。对于每个数字,遍历其32位中的每一位,更新bitCount数组。

  2. 寻找结果:遍历bitCount数组,如果某一位的计数不是M的倍数,那么这位一定属于那个出现K次的数。

  3. 重建结果:将这些位组合起来得到目标数字。

2)代码

	public static int findTimesNum(int[] arr, int K, int M) {int[] bitCount = new int[32];for(int i : arr) {for(int j = 0; j < 32; j++) {if((i & (1 << j)) != 0) {bitCount[j]++;}}}int result = 0;for(int i = 0; i < 32; i++) {if(bitCount[i] % M != 0) {// 不能被M整除,则有出现K次的数在这一位为1result |= (1 << i);// 将最终结果的这一位置为1}}return result;}

运行结果:


http://www.ppmy.cn/devtools/132034.html

相关文章

代码随想录算法训练营Day.3| 移除链表元素 设计链表 反转链表

长沙出差ing&#xff0c;今天的核心是链表&#xff0c;一个比较基础且重要的数据结构。对C的指针的使用&#xff0c;对象的创建&#xff0c;都比较考察&#xff0c;且重要。 203.移除链表元素 dummyNode虚拟头节点很重要&#xff0c;另外就是一个前后节点记录的问题。但是Leet…

华为HarmonyOS借助AR引擎帮助应用实现虚拟与现实交互的能力3-获取设备位姿

设备位姿描述了物体在真实世界中的位置和朝向。AR Engine提供了世界坐标下6自由度&#xff08;6DoF&#xff09;的位姿计算&#xff0c;包括物体的位置&#xff08;沿x、y、z轴方向位移&#xff09;和朝向&#xff08;绕x、y、z轴旋转&#xff09;。通过AR Engine&#xff0c;您…

Java自动点名器实现案例详解

Java自动点名器实现案例详解 在教学管理中&#xff0c;点名是一项重要的任务。随着技术的发展&#xff0c;使用编程语言实现自动化的点名器不仅可以提高效率&#xff0c;还能增加课堂的互动性和趣味性。本文将详细介绍三个案例&#xff0c;分别是简单随机点名器、带有权重的随…

在使用Alt+Tab切换程序时 Windows 11 24H2会出现黑屏

Windows 中的 Alt-Tab 快捷键组合可帮助您在多个活动应用窗口之间循环跳转。 但是&#xff0c;在 Windows 11 24H2 更新中&#xff0c;该快捷键被弄坏了&#xff0c;如果按下组合键&#xff0c;就会触发黑屏。 虽然 Alt Tab 功能不会停止工作&#xff0c;但黑屏会持续 10 秒钟…

有Bootloader,为什么还要BROM?

有Bootloader&#xff0c;为什么还要BROM? 不少硬件平台都提供类似Boot ROM或者PBL(高通平台)固化的一段程序&#xff0c;出厂后用户一定不能修改。BROM可以引导Bootloader程序。大家知道&#xff0c;每个可启动的平台都会在存储设备&#xff0c;例如EMMC/NAND/UFS保存Bootloa…

工作管理实战指南:利用Jira、Confluence等Atlassian工具打破信息孤岛,增强团队协作【含免费指南】

如果工作场所存在超级反派&#xff0c;其中之一可能会被命名为“信息孤岛”&#xff0c;因为它们能够对公司的生产力和协作造成严重破坏。当公司决定使用太多互不关联的工具来完成工作时&#xff0c;“信息孤岛”就会出现&#xff0c;导致团队需要耗费大量时间才能就某件事情达…

LLMs之Calculate:利用大语言模型技术基于文本内容实现数字计算能力的简介、常用方法、代码实现之详细攻略

LLMs之Calculate:利用大语言模型技术基于文本内容实现数字计算能力的简介、常用方法、代码实现之详细攻略 导读:在基于大语言模型(LLM)技术实现数字计算能力的背景下,文本内容的理解和计算过程涉及多个领域的交叉技术,包括自然语言处理(NLP)、机器学习、以及数值计算。…

Caché/IRIS file2Xml 一个将文件转换成Studio导出的xml格式的工具

file2Xml 一个将文件转换成Studio导出的xml格式的工具 通过此工具可以将本地文件转换成xml格式文件&#xff0c;然后通过Studio导入到服务器中&#xff0c;而不再需要其他工具将文件传至服务器。 下面以为ensemble2016自带的一个示例界面增加背景图为例。 http://localhos…