1

蓝桥杯——想不到的位运算 - lx-Meteor

 1 year ago
source link: https://www.cnblogs.com/lx-meteor/p/17016484.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client
  • 笔者准备参加蓝桥杯，所以再次记录自己的学习心得。
  • 我会将自己的算法学习之路用博客进行记录，并将学习思想进行分享。
  • 希望大家如果看文章的话，可以认真阅读题目，并进行思考。
  • 希望和大家一起共同成长
    2816773-20221231124556351-135146073.png

二、奇妙的异或

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过来的！
    • 

  • 尊重每一位学习知识的人，同时也尊重每一位分享知识的人。
    • 

  • 😎你的点赞与关注，是我努力前行的无限动力。🤩
    • 




__EOF__

        

        

            

                report
            

        

    







        
Recommend

        



                

    
About Joyk

    
 





Aggregate valuable and interesting links.

Joyk means Joy of geeK