02-异或算法

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

2. 异或算法

2.1 异或基础

  1. 0^N == N N^N == 0;
  2. 记为无进位相加即可,1+1 = 0;
  3. 异或运算满足交换律和结合。

2.1.1 不用额外变量交换两个数

解法:aba = b,abb = a。

2.1.2 找出现奇数次的数

1. 题目

​ 一个数组中有一种数出现了奇数次,其他数都出现了偶数次,怎么找到并打印这种数。

2. 思路

​ 数组里每个元素都异或,两两相消,就只剩下奇数次的那个数

3. 代码文章来源地址https://www.toymoban.com/news/detail-746154.html

public static void main(String[] args) {
    int[] arr = {1,3,4,1,3,4,1,3,4,5,1,3,4};
    int ans = 0;
    for (int i = 0; i < arr.length; i++) {
        ans ^= arr[i];
    }
    System.out.println(ans);
}

2.2 提取右侧(最低位)的1

1. 题目

​ 怎么把一个int类型的数,提取出最右侧(最低位)的1来

2. 思路

1. 取反加一再和原来相与 a&(~a+1)

​ 取反:这样每一位都不一样,之前的0位置都变成了1,假设此时的值为b。

​ 加一:这样在右面+1就可以让他一直进位直到第一个0(也就是没取反的时候的1的位置),假设此时值为c。

​ 相与:此时c的状态是最低的1往右的值都是0,最低一位的1的位置和a相同,这一位再往右每一个都是不一样的,所以相与之后,直接就可以得到结果。

注意: ~a+1 就等于-a,所以也可以写成a&(-a)

2. 直接暴力

​ 先找位置,然后再把1右移

3. 代码

取反加一:

System.out.println((a&(~a+1)));
System.out.println((a&(-a)));

暴力:

private static int findRightest(int a) {
    int rightPos = 0;
    // 找最低位的1
    for(int i = 0; i < 32; i++){
        if((a & 1) == 1){
            rightPos = i;
            break;
        }
        a = a>>1;
    }

    a = 1;
    // 右移
    for (int i = 0; i < rightPos; i++) {
        a = a << 1;
    }
    System.out.println(a);
    return a;
}

2.3 找到两种奇数数

1. 题目

一个数组中有两种数出现了奇数次,其他数都出现了偶数次,怎么找到并打印这两种数

2. 思路

​ 全部异或,只留下eor = a^b

​ 因为a != b,所以二进制的ab至少有一位不一样,即eor != 0,也就是至少存在一位为1。

​ 既然有一位为1,代表a,b在这一位不同(异或:同0异1),那么就可以通过这一位来区分数组。

​ 这一位为0的放一边,为1的放一边,分别异或,这样得到的数就可以区分出来ab了。

只要是eor有一位为1就可以区分,具体是哪个无所谓,所以不妨设是最右侧的一个。

3. 代码

private static int[] getAB(int[] arr) {
    // 先异或,得到eor=a^b;
    int eor = 0;
    for (int i = 0; i < arr.length; i++) {
        eor ^= arr[i];
    }
    // 对于ab,最右侧一位的1提取出来
//        System.out.println(eor);
    int rightest = eor&(-eor);
//        System.out.println(rightest);
    // 根据这一位来区分属于谁
    // 不妨设a在这位为0,b在这位为1
    int[] ans = new int[2];
    for (int i = 0; i < arr.length; i++) {
        if((arr[i] & rightest) == 0){
            ans[0] ^= arr[i];
        }else{
            ans[1] ^= arr[i];
        }
    }
    return ans;
}

2.4 找到出现k次的数

1. 题目

​ 一个数组中有一种数出现K次,其他数都出现了M次,M > 1, K < M,

​ 要求:找到出现了K次的数,额外空间复杂度O(1),时间复杂度O(N)

2. 思路

​ 利用长度为32的数组,记录下每一位置出现1的次数,模M除K就得到二进制的所求数,再转为十进制。

3. 代码

private static int findKTimes(int[] arr, int m, int k) {
    int[] times = new int[32];
    // 记录所有数的32位的出现的次数
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < times.length; j++) {
            if((arr[i]&(1<<j)) != 0){
                times[j] ++;
            }
        }
    }
//        Arrays.stream(times).forEach(System.out::println);
    // 所有数%m/k 得到的数组合成int
    int ans = 0;
    for (int i = 0; i < times.length; i++) {
        times[i] = times[i]%m/k;
    }

    // 组合成int
    for (int i = 0; i < times.length; i++) {
        // cur = 1 1 0 1
        // times = 1 0 1 1
        ans += (times[i]<<i);
    }
    return ans;
}

到了这里,关于02-异或算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 异或运算在算法中的神奇应用

    两个二进制数进行异或运算时,每一位上的数相同则结果为0,不同则结果为1。 简单记:异或就是二进制的无进位相加。 还有个同或运算:相同为1,不同为0,和异或是反的。 任何数与0异或,结果还是这个数:0^n=n 任何数与自身异或,结果都是0:n^n=0 异或运算满足交换律和

    2024年04月08日
    浏览(47)
  • Java中异或操作和OTP算法

    最近在研究加密算法,发现异或操作在加密算法中用途特别广,也特别好用。下面以Java语言为例,简单记录一下异或操作,以及在算法中的使用,包括常用的OTP算法。 一,异或操作特征 1, 相同出0,不同出1 换种说法是:无进位进行相加 0 ^ 0 = 0 0 ^ 1 = 1 1 ^ 0 = 1 1 ^ 1 = 0 比

    2024年02月10日
    浏览(38)
  • 代码随想录-哈希表02 第454题.四数相加II&383. 赎金信&第15题. 三数之和&第18题. 四数之和

    第454题.四数相加II 第454题.四数相加II 条件:四个数组中分别取一个,相加和为0,求满足条件的元组个数 思路使用1个map,mapA保存 s1 s2中相加和及其出现次数 遍历s3 s4,去判断是否满足 0 - (s3[i] + s4[j]) 在mapA中,并统计出现次数 383. 赎金信 383. 赎金信 题目要求,s1 是否能由s

    2024年02月12日
    浏览(45)
  • C++字典树算法:找出强数对的最大异或值 II

    数学 字典树 给你一个下标从 0 开始的整数数组 nums 。如果一对整数 x 和 y 满足以下条件,则称其为 强数对 : |x - y| = min(x, y) 你需要从 nums 中选出两个整数,且满足:这两个整数可以形成一个强数对,并且它们的按位异或(XOR)值是在该数组所有强数对中的 最大值 。 返回数

    2024年02月05日
    浏览(50)
  • 【算法详解】力扣415.字符串相加

    力扣链接:力扣415.字符串相加 给定两个字符串形式的非负整数 num1 和num2 ,计算它们的和并同样以字符串形式返回。 你不能使用任何內建的用于处理大整数的库(比如 BigInteger), 也不能直接将输入的字符串转换为整数形式。 示例 1: 输入:num1 = “11”, num2 = “123” 输出:

    2024年01月22日
    浏览(44)
  • LeetCode算法题---两数相加(二)

    给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。 请你将两个数相加,并以相同形式返回一个表示和的链表。 你可以假设除了数字 0 之外,这两个数都不会以 0 开头。 示例 1:   示例 2: 示例

    2024年02月09日
    浏览(47)
  • 【算法Hot100系列】两数相加

    💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学习,不断总结,共同进步,活到老学到老 导航 檀越剑指大厂系列:全面总

    2024年02月04日
    浏览(42)
  • 算法刷题-哈希表-四数相加

    需要哈希的地方都能找到map的身影 力扣题目链接 给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ,使得 A[i] + B[j] + C[k] + D[l] = 0。 为了使问题简单化,所有的 A, B, C, D 具有相同的长度 N,且 0 ≤ N ≤ 500 。所有整数的范围在 -2^28 到 2^28 - 1 之间,最终结果

    2024年02月08日
    浏览(42)
  • LeetCode 算法 2.两数相加(python版)

    给你两个 非空 的链表,表示两个非负的整数。 它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。 请你将两个数相加,并以相同形式返回一个表示和的链表。 你可以假设除了数字 0 之外,这两个数都不会以 0 开头。

    2024年01月21日
    浏览(39)
  • 【算法】Add Two Numbers 两数相加

    给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。 请你将两个数相加,并以相同形式返回一个表示和的链表。 你可以假设除了数字 0 之外,这两个数都不会以 0 开头。 每个链表中的节点数在范围

    2024年02月11日
    浏览(47)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包