• 位运算的应用--->位图


    首先我们先了解一下什么是位图。

    首先我们知道一个int类型的数据再内存中是以二级制的方式储存,但是怎么用二进制的方式来存储数据,那么就把每个二进制位当作标记,用来标记第每个数字是否存储,那么如果是二进制的话那么我们就只能标记0~31中,其中的数字是否有进行存储,那么如果我们需要进行存储更多,那么我们就需要运用到数组,因为数组是一份连续的存储空间。假如我们需要存储0~63,那么我们就需要一个int[2],的数组来进行存储,同时还可以选择一个long类型的数据来进行存储。

    我们只需要选择一个存储的最大的数据,我们就可以选择我们存储的最大类型。

    位图简单的就是利用二进制来进行做标记,0--->没有这个数,1--->有这个数。

    第一个二进制表示,0这个数有没有,

    第二个二进制表示,有没有1这个数,

    .............

    第八个二进制位表示,有没有8这个数,

    .............

    第二十个二进制表示,有没有20这个数。

    这样我们就可以利用二进制位来表示我们的数字集合------>(BitMap 位图)。

    集合的成员属性

    1. private long[] bits;
    2. private int max;
    3. private int min;

    首先我么利用bits这个数组来表示我们一连串的二进制位,同时我们设置了最大值和最小值,用来确定我们所需要的的集合大小

    1. public BitMap(int max){
    2. this(max,0);
    3. }
    4. public BitMap(int max,int min){
    5. this.max = max;
    6. this.min = min;
    7. bits = new long[(max-min+64)>>6];
    8. }

    我们通过最大值和最小值来进行判断我们所需要的最小空间。

    首先我们先计算max到min之间有几个数字(包括最大值和最小值)。

    max-min+1

    同时我们要知道一个long类型时是64个比特位,所以我们要计算我们的数组需要多大,所以我们就需要整体除以64。

    但是当我们我们最大值和最小值之间的数字是小于64的时候相除会导致数组的无法统计部分数字。

    所以我们进行成体加上63,这样就能保证能够满足条件。

    位图的添加元素

    1. public void add(int value){
    2. value = value-min;
    3. bits[(value)>>6] |= (1L<<(value & 63));
    4. }

    首先我们要根据我们需要的元素进行判断我们需要添加的元素在第几个long。

    同时我们要进行取模操作。但是我们并不是直接使用取模操作符。

    例如:

    二进制数 1100101011101101010

    63------->0000000000000111111

    进行&操作00000000000101010

    相当于大于64的前面全部忽略。(运用位运算代替取模操作是能运用到2^n)

    用1L向前左移value的取模数。

    相当于前1000000(64)的数字用来确定在第几个long,

    后面的数字用来确定这个数的位置long的第几个bit。

    删除

    1. public void delete(int num){
    2. if(num>=min && num<=max){
    3. num = num-min;
    4. bits[num>>6] &= ~(1L << (num & 63));
    5. }
    6. }

    首先我们需要知道删除的数字是否在最大值和最小值之间。

    同时我们要在知道这个数字在第几个long,

    同时我们用取模之后的数字进行进行判断在第几个比特位,同时我们依然是选择之前的方法找到。

    但是删除就需要将找到位置后的数字进行取反。例如:

    找到第几个比特位之后:

    000000000010000000000000000

    取反之后

    111111111101111111111111111

    原本bits[(value)>>6] 的数字

    010101100111000010010010101

    进行&操作

    010101100011000010010010101

    判断某个数是否存在。

    1. public boolean conatins(int num){
    2. if(num>max && num
    3. return false;
    4. }else{
    5. num = num-min;
    6. return (bits[num>>6] & (1L << (num & 63))) !=0;
    7. }
    8. }

    首先我们需要和之前一样找到我们需要判断的num所在的第几个long。

    然后我们用之前添加数字的方式找到该数所对应的比特位

    我们再用整个long与(1L<<(num & 63))进行&操作,然后判断是不是为0.

    1. import java.util.HashSet;
    2. public class BitMap {
    3. private long[] bits;
    4. private int max;
    5. private int min;
    6. public BitMap(int max){
    7. this(max,0);
    8. }
    9. public BitMap(int max,int min){
    10. this.max = max;
    11. this.min = min;
    12. bits = new long[(max-min+64)>>6];
    13. }
    14. public void add(int value){
    15. value = value-min;
    16. bits[(value)>>6] |= (1L<<(value & 63));
    17. }
    18. public void delete(int num){
    19. if(num>=min && num<=max){
    20. num = num-min;
    21. bits[num>>6] &= ~(1L << (num & 63));
    22. }
    23. }
    24. public boolean conatins(int num){
    25. if(num>max && num
    26. return false;
    27. }else{
    28. num = num-min;
    29. return (bits[num>>6] & (1L << (num & 63))) !=0;
    30. }
    31. }
    32. public static void main(String[] args) {
    33. boolean flag = true;
    34. int max = 99999999;
    35. int min = 999;
    36. for(int j = 0;j<5;j++){
    37. do{
    38. max = (int)(Math.random() * (max+1));
    39. min = (int)(Math.random() * (min+1));
    40. }while (max<=min);
    41. BitMap map = new BitMap(max,min);
    42. HashSet set = new HashSet<>();
    43. int testTime = 50000000;
    44. int num = 0;
    45. for(int i = 0;i
    46. do{
    47. num = (int)(Math.random() * (max+1));
    48. }while(num
    49. double decide = Math.random();
    50. if(decide<0.33){
    51. map.add(num);
    52. set.add(num);
    53. }else if(decide<0.66){
    54. map.delete(num);
    55. set.remove(num);
    56. }else{
    57. if(map.conatins(num)!=set.contains(num)){
    58. flag = false;
    59. break;
    60. }
    61. }
    62. }
    63. for(int t = min; t<= max; t++){
    64. if(map.conatins(t) !=set.contains(t)){
    65. flag = false;
    66. break;
    67. }
    68. }
    69. }
    70. System.out.println(flag ? "Nice" : "Fucking fucked");
    71. }
    72. }

  • 相关阅读:
    阿桂天山的技术小结:Flask实现对Ztree树状节点的增改删操作
    【遗留】等待谁来帮助一下,webSocket的messagingTemplate跨域问题
    IDEA Properties 文件亂碼怎麼解決
    如何选择线程数量
    everything常用搜索命令
    【云计算】虚拟私有云 VPC
    深入理解控制反转IOC和依赖注入
    基于java+swing+mysql实现的仓库商品管理系统
    Git 的基本使用(笔记)
    关于信息安全软考的记录5
  • 原文地址:https://blog.csdn.net/weixin_61652218/article/details/126324852