异或
2022/3/11 23:18:46
本文主要是介绍异或,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
1 基本概念
1.1 符号
异或是一种二进制的位运算,符号以 XOR 或 ^ 表示。
1.2 运算规则
相同为0,不同为1,即
1 ^ 1 = 0
0 ^ 0 = 0
1 ^ 0 = 1
由运算规则可知,任何二进制数与零异或,都会等于其本身,即 A ^ 0 = A。
1.3 异或性质
(1)交换律: A ^ B = B ^ A
(2)结合律: ( A ^ B ) ^ C = A ^ ( B ^ C )
(3)自反性: A ^ B ^ B = A (由结合律可推: A ^ B ^ B = A ^ ( B ^ B ) = A ^ 0 = A)
2.运用
2.1 变量交换
示例:将 a 和 b 两个变量值交换,例如: a = 3,b = 7,交换后,a = 7,b = 3。
1 // 常规方法 2 int temp = a; // temp = 3 3 a = b; // a = 7 4 b = temp; // b = 3 5 6 // 异或方法 7 a = a ^ b; // a = 3 ^ 7 8 b = a ^ b; // b = (3 ^ 7) ^ 7 = 3 ^ (7 ^ 7) = 3 9 a = a ^ b; // a = (3 ^ 7) ^ (3 ^ 7 ^ 7) = (3 ^ 3) ^ (7 ^ 7) ^ 7 = 7
2.2 排除偶次重复
示例:在一个整数数组中,仅存在一个不重复的数字,其余数字均出现两次(或偶数次),找出不重复数字。
P1469 找筷子 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
1 int n; 2 scanf("%d",&n); 3 4 int ans=0; 5 for(int i=1;i<=n;i++) 6 { 7 int x; 8 scanf("%d",&x); 9 ans^=x; 10 } 11 12 printf("%d\n",ans);
2.3 排除偶次重复变种
示例:将数字1-999存放在一个大小为1000的数组中,其中只有一个数字重复出现两次,找出重复数字。
将1000个整数依次异或运算,最终结果就是重复的数字,相当于重复数字与0进行异或,得到其本身。
1 int result = 0; 2 for (int index = 0; index < numArray.length; index++) { 3 result = result ^ numArray[index]; 4 } 5 return result;
2.4 只出现一次的数字
题目:给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。
思路:
(1) 先通过一次异或操作,重复元素会被抵消,最终结果相当于两个单次出现的元素(分别记为one和two)的异或值;
(2) 由异或规则可知,若两个元素one和two的异或值的某二进制位为1,则表示两个元素在该二进制位上的值不同,即分别为1和0,找到其中一个满足条件(为1)的二进制位(记为bitValue);
(3) 根据(2)找到的二进制位bitValue,可以将原数组分成两个部分,one 和 two 分别在两个部分,而相同的重复元素也会被分到同一个部分(因为其相应的二进制位的值是相同的);
(4) 对于两个部分再次进行异或操作,即相当于 排除偶次重复 问题,最终可以得到两个题解。
1 class Solution { 2 3 public int[] singleNumber(int[] nums) { 4 5 // 通过异或操作,最终结果等于两个单次出现的元素的异或值。 6 int filterResult = 0; 7 for (int num : nums) { 8 filterResult ^= num; 9 } 10 11 // 计算首个为1(从右侧开始)的二进制位的值 12 int bitValue = filterResult & (filterResult - 1) ^ filterResult; 13 14 // 以首个为1的二进制位将原数组分为两个部分并分别进行异或运算,最终结果为两个题解。 15 int oneResult = 0, twoResult = 0; 16 for (int num : nums) { 17 if ((num & bitValue) > 0) { 18 oneResult ^= num; 19 } else { 20 twoResult ^= num; 21 } 22 } 23 24 return new int[]{oneResult, twoResult}; 25 } 26 }
这篇关于异或的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?
- 2024-05-09企业src漏洞挖掘-有意思的命令执行