比较好的国外网站建设公司,wordpress短代码可视化,宿迁做网站 宿迁网站建设,有关于网站建设的论文这里写自定义目录标题 异或运算题目1题目2 本篇是关于异或#xff08;^#xff09;运算的运用。后期看算法过程中如果再碰到异或的都会收录到本篇中
异或运算
在逻辑学中#xff0c;逻辑算符异或#xff08;exclusive or#xff09;是对两个运算元的一种逻辑析取类型^运算的运用。后期看算法过程中如果再碰到异或的都会收录到本篇中
异或运算
在逻辑学中逻辑算符异或exclusive or是对两个运算元的一种逻辑析取类型符号为 XOR 或 EOR 或 ⊕编程语言中常用^。但与一般的逻辑或不同异或算符的值为真仅当两个运算元中恰有一个的值为真而另外一个的值为非真。转化为命题就是“两者的值不同”或“有且仅有一个为真”
true ^ true false
false ^ false false
true ^ false true
同理
1 ^ 1 0
0 ^ 0 0
1 ^ 0 1且满足两个特性交换律、结合律、归零律、恒等律
交换律A ^ B B ^ A
结合律(A ^ B) ^ C A ^ (B ^ C)
归零律A ^ A 0
恒等律A ^ 0 A有了归零率和结合律我们就可以轻松证明
自反A ^ B ^ B A ^ 0 A题目1
题目给定一个数组其中只有一个数出现奇数次其他都出现偶数次打印奇数次的数。 解法结合律和归零律 例子int[] array {1, 2, 2, 3, 3, 4, 4, 5, 5} 输出 1 思想 a ^ b ^ c ^ a ^ d ^ b ^ c ^ d ^ e ^ e ^ e ^ f ^ f a ^ a ^ b ^ b ^ c ^ c ^ d ^ d ^ e ^ e ^ e ^ f ^ f //分组0 ^ 0 ^ 0 ^ 0 ^ 0 ^ 0 ^ e ^ 0 //两两归零e代码
public class FindOddOccurrenceNumberUsingXOR {public static int findOddNumber(int[] arr) {int result 0;for (int num : arr) {result ^ num;}return result;}public static void main(String[] args) {int[] array {1, 2, 2, 3, 3, 4, 4, 5, 5};int oddNumber findOddNumber(array);System.out.println(奇数个的数字是 oddNumber);}
}题目2
题目给定一个数组其中有两个数出现奇数次其他都出现偶数次打印奇数次的数。 解法结合律和归零律 例子int[] array {1, 2, 2, 3, 3, 3, 4, 4, 5, 5} 输出 1,3 思想 a ^ b ^ c ^ ba ^ 0 ^ c //两两归零a ^ cx知道这两个值异或的结果如何知道两个值呢自反 A ^ B ^ B A 对于X转成二进制后我们知道肯定有一位是1因为x a ^ c那么这一位为1的数不是a就是c仅为其中1个我们假设是a。那么对于整个数组所有数来说就分了两个阵营。
该位置为1该位置为0acde,n,f
最后一步判断因为其他数字都是偶数个所以^后都是0只有基数个的数字c^才是1。这样就能获取到a和c的值了。
代码
public class FindTwoOddOccurrenceNumbers {public static int[] findTwoOddNumbers(int[] arr) {int xorResult 0;for (int num : arr) {xorResult ^ num;}//xorResult最终的值是 5^1// 找到两个奇数个数字的异或结果中的某一位为 1 的位置讲解如下// 假如 xorResult 5 101// 减1取反后~(101-001) 011// 再和101取 001;// 此种算法就是获取一个数的最右一位的1int rightmostSetBit xorResult (~(xorResult - 1));int firstNumber 0;for (int num : arr) {//获取与其中一个基数个数字同位置都是1的数字if ((num rightmostSetBit) 1) {//其他数字都是偶数个都是0所以可以找到其中一个基数个数字firstNumber ^ num;}}//自反原则xorResult ^ firstNumber (5^1)^1 5;return new int[]{firstNumber, xorResult ^ firstNumber};}public static void main(String[] args) {int[] array {4, 2, 4, 5, 2, 3, 3, 1};int[] result findTwoOddNumbers(array);System.out.println(两个出现奇数次的数字是 result[0] 和 result[1]);}
}
