秀站 > 生活 > 正文

​异或什么意思

2023-05-25 17:55 来源:秀网 点击:

异或什么意思

异或什么意思异或特征

异或(^): 相同为0,不同为1

N ^ 0 = N

N ^ N = 0

符合交换律和结合律: a^b=b^a (a^b)^c=a^(b^c)

两数交换:

a=a^b;b=a^b;a=a^b;

只出现一次的数字

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

说明:

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

使用异或运算,将所有值进行异或异或运算,相异为真,相同为假,所以 a^a = 0 ;0^a = a因为异或运算 满足交换律 a^b^a = a^a^b = b 所以数组经过异或运算,单独的值就剩下了

package array;/** * @author Darling yu * @version 1.0 * @date 2022/9/12 18:03 * 只出现一次的数字:给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。 * 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗? */public class SingleNumber { public static void main(String[] args) {  int[] nums = {4,1,2,1,2};  Solution solution = new Solution();  System.out.println(solution.singleNumber(nums)); } static class Solution {  /*** 使用异或运算,将所有值进行异或* 异或运算,相异为真,相同为假,所以 a^a = 0 ;0^a = a* 因为异或运算 满足交换律 a^b^a = a^a^b = b 所以数组经过异或运算,单独的值就剩下了* @param nums* @return*/  public int singleNumber(int[] nums) {int reduce = 0;for (int num : nums) { reduce =  reduce ^ num;}return reduce;  } }}

出现奇数次的两个数字

只有两种数出现奇数次,其他的数都出现偶数次,找出出现奇数次的这两个数

package array;/** * @author Darling yu * @version 1.0 * @date 2022/9/12 18:03 * 出现奇数次的两个数字:给定一个非空整数数组,只有两种数出现奇数次,其他的数都出现偶数次,找出出现奇数次的这两个数。 * 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗? */public class SingleNumberII { public static void main(String[] args) {  int[] nums = {1, 1, 1, 2, 2, 3, 3, 3, 4, 4};  Solution solution = new Solution();  solution.singleNumberII(nums); } static class Solution {  /*** 假设出现奇数次的两个数是a和b* 将所有数进行异或,最终得到的reduce=a^b* 因为a b是不同的两个数,reduce!=0,那么reduce必定有一位上面是1,* 也就是a,b两个数至少在某一位上面,一个数是1,另一个是0* 通过对reduce取反加一,再对自己进行&运算,得到最右侧的1的位置* 说明a b在这个位置上一个数是1 另一个是0* 将数组中的每个数与该位置1进行&运算,如果等于0,那这些数中必定有a或者b,假设为a* 这些数进行异或之后,剩下的就是a* 再与reduce异或,a^reduce=a^a^b=b得到另一个数b** @param nums* @return*/  public void singleNumberII(int[] nums) {int reduce = 0;// 将所有数进行异或 最终得到的reduce=a^bfor (int num : nums) { reduce = reduce ^ num;}// reduce有一个位置上是1// 假设reduce=  1001100// ~reduce取反= 0110011// ~reduce+1=0110100// reduce & (~reduce+1)= 0000100int rightOne = reduce & (~reduce + 1); // 提取出最右侧的1int onlyOne = 0;for (int num : nums) { //(num & rightOne) == 0  或者(num & rightOne) == rightOne if ((num & rightOne) == 0) {// 说明num在reduce最右侧的1的位置上是0  onlyOne ^= num; }}System.out.println("一个数是:" + onlyOne);System.out.println("另一个数是:" + (onlyOne ^ reduce));  } }}

热门标签

最近文章