蓝桥杯——想不到的位运算

一、前言

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

二、奇妙的异或

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 

三、奇妙的运算

请实现一个函数,输入一个整数,输出该数二进制表示中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 

算法思想————解法二:

  • 可以采用该数-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过来的!
  • 尊重每一位学习知识的人,同时也尊重每一位分享知识的人。
  • 😎你的点赞与关注,是我努力前行的无限动力。🤩

文章来源于互联网:蓝桥杯——想不到的位运算

THE END
分享
二维码