算法通过村第十一关-位运算|黄金笔记|位运算压缩

---

前言

---

提示：如果谁对你说了地狱般的话，就代表了他的心在地狱。你不需要相信那样的话，就算对方是你的父母也一样。 --高延秀《远看是蔚蓝的春天》

位运算有个很重要的作用就是能用比较小的空间存储比较多的元素。能帮助我们处理一些海量场景下的处理问题。

这里留个问题，我们后面回继续讨论。（超大规模数据场景常见问题）

用4kb内存寻找重复元素

题目要求：给定一个数组，包含从1到N的整数，N最大位32000，数组可以还有重复值，且N的取值不定。若只有4Kb的内存可用，该如何打印数组中所有重复元素。

分析：本身是一道海量数据问题的热身题。如果去掉“只有4kb”的要求，我们可以先创建一个大小为N的数组，然后将这些数据放进来，但是这里数组最大为32KB，而题目有4KB的内存限制，我们就必须先确定该如何存放这个数组。

如果只有4KB的空间，那么只能寻址8 * 4 * 2 ^ 10 个比特，这个值比320000要大的，因此我们可以创建320000比特的位向量(比特数组)，其中一个比特位置就代表一个整数。

利用这个位向量，就可以遍历访问整个数组。如果发现数组元素是v，那么就将位置位v的设置位1，碰到重复元素，就输出一下。

下面的代码也仅供参考，你看看就行了，也不用会写，面试的时候也不会让你作测试（也没法作测试）

public class FindDuplicatesIn32000{
    public void checkDoublicates(int array[]){
        BitSet bs = new BitSet(320000);
        for(int i = 0; i< array.length; i++){
            int num = array[i];
            int num0 = num - 1;
            if(bs.get(num0)){
                System.out.println(num);
            }else {
                bs.set(num0);
            }
        }
    }
    class BitSet{
        int[] bitSet;
        
        public BitSet(int size){
            this.bitSet = new int[size >> 5]; // 除以32
        }
        boolean get(int pos){
            int wordNumber = (pos >> 5);
            int bitNumber = (pos & 0x1f); // 取模32
            return (bitset[wordNumber] & (1 << bitNumber)) != 0;
        }
        
        void set(int pos){
            int wordNumber = (pos >> 5);
            int bitNumber = (pos & 0x1f);// 取模32
            bitset[wordNumber] | = 1 << bitNumber;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

---

总结

提示：位运算；数据压缩处理；海量数据处理模型；大数据压缩；二进制处理数据

---

如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ ("▔□▔)/

如有不理解的地方，欢迎你在评论区给我留言，我都会逐一回复 ~

也欢迎你 关注我 ，喜欢交朋友，喜欢一起探讨问题。