登录/注册
qgyh
2158
占位
1
占位
0
浏览量
占位
粉丝
占位
关注
蓝桥杯——想不到的位运算
qgyh
2023-01-03 09:57:10 2023-01-03
3
0

一、前言

  • 笔者准备参加蓝桥杯，所以再次记录自己的学习心得。
  • 我会将自己的算法学习之路用博客进行记录，并将学习思想进行分享。
  • 希望大家如果看文章的话，可以认真阅读题目，并进行思考。
  • 希望和大家一起共同成长

二、奇妙的异或

1-1000这1000个数放在含有1001个元素的数组中，只有唯一的一个元素值重复，其它均只出现一次。每个数组元素只能访问一次，设计一个算法，将它找出来；不用辅助存储空间，能否设计一个算法实现？

前置知识：

  • 一个数与本身进行异或，结果为0。A ^ A = 0
  • 任何数与零进行异或，结果为本身。 B ^ 0 = B

算法思想：

  • 通过阅读题目，我们可以利用异或性值，将1——1000这组数据复制一份，与原先的这组数进行异或，那么我们重复的元素就会出现3次，而其他元素只出现两次。
  • 所以我们可以得出最后的结果
// A ^ A = 0
// B ^ 0 = B
public class 唯一成对的数 {
    public static void main(String[] args) {
        int N = 101;
        int[] arr = new int[N];
        for(int i = 0; i < arr.length-1; i++) {
            arr[i] = i+1;
        }
        // 最后一个随机数
        arr[arr.length-1] = new Random().nextInt(N);
        // 随机下标
        int index = new Random().nextInt(N);
        // 随机交换
        Utils.swap(arr, index, arr.length-1);
        System.out.println(Arrays.toString(arr));
        int res = 0;
        // 让 res 与 1..100进行异或运算
        for(int i = 1; i <= N-1; i++) {
            res = res ^ i;
        }
        // 让 1..100和多的一位数，与res进行异或，当两个1..100进行异或时为0，所以答案就是剩下的最后一个值
        for(int i = 0; i < N; i++) {
            res = res ^ arr[i];
        }
        System.out.println(res);
    }
}

三、奇妙的运算

请实现一个函数，输入一个整数，输出该数二进制表示中1的个数。 例如9的二进制1001，有2个1

前置知识：

  • 与运算 1 & 1 = 1、1 & 0=0
  • 移位

算法思想————解法一：

  • 我们可以让该数与1从右至左进行与运算。这样如果结果为1，那么就是1，我们在进行判断是否相等。
  • 每一次都需要将我们的1左移一位，也相当于对该二进制数进行扫描
public class 二进制1的个数 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        System.out.println(Integer.toString(N,2));
        int count = 0;
        // 让1移位，与二进制每一个数进行 与运算
        for (int i = 0; i < 32; i++) {
            if((N & (1 << i)) == (1 << i)) {
                count++;
            }
        }
        System.out.println(count);
    }
}

算法思想————解法二：

  • 可以采用该数-1操作，然后与原来的数进行与运算，这样我们可以消除最右边的1，直接把1全部消掉，结果为0为止。
// 因为二进制-1后和 原先的值进行 与运算，会消除最右边的1
        System.out.println("解法二-----------------");
        count = 0;
        while(N!=0) {
            N = (N-1)&N;
            count++;
        }
        System.out.println(count);

四、简单的代码

用一条语句判断一个整数是不是2的整数次方。

算法思想：

  • 我们知道2的整数次方的二进制，应该是只含有一个1的
  • 所以本题我们就可以变解为求二进制中是否存在一个1
  • 利用我们上面所学的求1的个数，那么我们很快就可以解决。
if( ((N-1)&N)) == 0) return true;

五、复杂的运算

数组中只有一个数出现了1次，其他的数都出现了k次，请输出只出现了1次的数。

前置知识：

  • 2个相同的2进制数做不进位加法，结果为0
  • 10个相同的10进制数做不进位加法，结果为0
  • k个相同的k进制数做不进位加法，结果为0

算法思想：

  • 所以本题我们可以将出现k次的数，转换为k进制，然后进行加法运算。
  • 我们还需要将数字进行翻转，这样才能够保证我们在做加法运算时，最低位是对齐的。
  • 其实我们可以采用哈希表速速解决战斗，但是我们学习的是位运算的思想。

六、结尾

  • 对于蓝桥杯位运算知识内容就总结这么多，若想深入学习等待后续更新。
  • 我将会继续更新关于蓝桥杯方向的学习知识，感兴趣的小伙伴可以关注一下。
  • 文章写得比较走心，用了很长时间，绝对不是copy过来的！
  • 尊重每一位学习知识的人，同时也尊重每一位分享知识的人。
  • 😎你的点赞与关注，是我努力前行的无限动力。🤩
暂无评论