位运算 | （三）位运算之位图使用及讲解

前言

本文将讲解位运算中一种比较实用的算法：位图，不同于此系列前两篇文章（第一篇、第二篇）主要讲位运算的基础知识和技巧，内容比较散且杂，本文讲只讲位图这一个知识点，此外，还需要注意的是，这个位图，并不是指点阵图像，不是位图和矢量图中那个位图，而是指一种数据结构，如果你知道Map数据结构的话，可以认为这里的位图就类似与<K, V>映射的结构，只不过这里的K是数字的每一个位，V则只有 0 和 1 这两种值，下面就来通过几个例子让你对位图有一个整体的认识。

找到一千万个数中缺失的数

如题，假如这这一千万个数的范围也是在[1, 1 000 000)，那么我们如何快速找到缺失的数呢？最简单粗暴的算法就是直接使用一个HashSet存储这些数，然后再从[1, 1 000 000)进行挨个遍历即可，代码如下：

// 随机生成一千万个[1, 1000000)之间的数
IntStream stream = new Random().ints(10000000, 1, 1000000);
// 保存到 HashSet 中
Set<Integer> set = stream.boxed().collect(Collectors.toSet());
// 遍历输出缺失的数
IntStream.range(1, 1000000)
         .filter(val -> !set.contains(val))
         .forEach(System.out::println);

不过由于我们保存的只是普通的整数类型，所以我们其实可以直接使用一个长度为10000001的布尔数组，可以加快运算的速度，代码稍作修改即可：

IntStream stream = new Random().ints(10000000, 1, 1000000);
boolean[] map = new boolean[10000000];
stream.forEach(val -> map[val] = true);
IntStream.range(1, 1000000)
         .filter(val -> !map[val])
         .forEach(System.out::println);

但是以上两种方法都浪费一些存储空间，即使是布尔数组也使用了 1 byte(8位，参照JVM规范的定义，并不一定是 1 个字节)保存一个数的标志位，但是通过使用位图，我们只需要 1 Bit即可保存一个数是否存在的标志，这样就只需要 1 / 8 的内存即可存储这些数的标志（如果布尔数组每个布尔数为1 byte的话），这里以long为例，一个long为8字节，64位，因此我们就可以用一个long的64位来标记连续的64个数中每一个数的存储标志，最终我们使用 10000000 / 64 + 1个long类型的数即可存储所有的数据存在标志，在展示最终的代码之前，先探讨一下一些小细节：

由于初始时数的每一位都为0，因此我们通过将一个数的某位置为1来代表某数存在，使用n |= (1 << pos)即可，但是由于一个long只有64位，因此我们在置位的时候，还需要先计算该数对应long数组中哪一个long数据的哪一位，下面就来通过代码来展示这一思路：

IntStream stream = new Random().ints(10000000, 1, 1000000);
// 声明一个可以容纳一千万个数的标志位的 long 数组
long[] map = new long[10000000 / 64 + 1];
stream.forEach(val -> {
    // 计算数对应数组的下标及对应的位
    int index = val >> 6;
    int pos = val & 63;
    map[index] |= (1L << pos);
});
IntStream.range(1, 1000000).filter(val -> {
    // 若标志位为0则表明该数不存在
    int index = val >> 6;
    int pos = val & 63;
    return (map[index] & (1L << pos)) == 0;
}).forEach(System.out::println);

尽管使用位图的时候，编码较上述两种方法更复杂一些，但是在空间与时间上都得到了很大的提升（由于我们可以通过位运算轻松的得到index和pos，所以这里才比较快，如果使用/和%，编译器再没有优化的话，时间可能会慢一些，不过空间占用的减少，这点还是可以确信的）。

注意

其实，我们还可以简化以上的代码，并不需要通过val & 63计算pos，因为当pos大于数位的长度时，在Java中自动会只取pos的低64 位（如果是int，则是32），不过在C语言中则可能不行，关于移位的细节可以查看《深入理解计算机系统》中文版的第 64 页。因此我们的代码中可以省略对pos的计算，只需要计算index即可，简化后的代码如下：

IntStream stream = new Random().ints(10000000, 1, 1000000);
long[] map = new long[10000000 / 64 + 1];
stream.forEach(val -> map[val >> 6] |= (1L << val));
IntStream.range(1, 1000000)
    .filter(val -> map[val >> 6] & (1L << val) == 0)
    .forEach(System.out::println);

子集

该题源自LeetCode，具体题目如下： 给定一组不含重复元素的整数数组nums，返回该数组所有可能的子集（幂集）。 说明：解集不能包含重复的子集。

示例: 输入: nums = [1,2,3] 输出: [[3],[1],[2],[1,2,3],[1,3],[2,3],[1,2],[]]

来源：力扣（LeetCode） 链接：leetcode-cn.com/problems/su… 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这里直接给出思路：

仔细研究子集的特点，可以发现一个不含重复元素的整数数组nums的所有子集，即对应着[0, 2 ^ len - 1)（这里的len代表数组的长度，^代表乘方运算）的所有状态，我们很容易得到[0, 8)之间每个数的二进制表达形式：

假设我们用1代表某数存在，否则不存在，那么000即对应着[]的情况，111对应着[1, 2, 3]的情况，因此我们就可以利用位图的思想去解决这道题：

public List<List<Integer>> subsets(int[] nums) {
    int count = nums.length;
    int n = 1 << count;
    List<List<Integer>> ans = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        List<Integer> list = new ArrayList<>();
        int temp = i;
        for (int num : nums) {
            if ((temp & 1) == 1) {
                list.add(num);
            }
            temp >>= 1;
        }
        ans.add(list);
    }
    return ans;
}

可怜的小猪

这一道题也改编自LeetCode，这里只讨论最简单的情况： 有 100 只水桶，其中有且只有一桶装的含有毒药，其余装的都是水。它们从外观看起来都一样。如果小猪喝了毒药，一小时后它会就会死去。如果需要你弄清楚哪只水桶含有毒药，你最少需要多少只猪（猪死多少无所谓，需要找到的时间尽可能得快）？

来源：力扣（LeetCode） 链接：leetcode-cn.com/problems/po… 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这里直接给出答案和思路，我们只要 7 只小猪即可，思路如下： 先将这 100 只水桶从[0, 100)进行编号，然后我们知道 7 位二进制可以表示000 0000 - 111 1111这 128 个数，我们只需要让这 7 只小猪分别喝[0, 100)中在其位上为 1 的水桶的水即可，举例来说，假如有第 63 号水桶，对应二进制为011 1111，那么我们就让 0 – 6号小猪去喝这桶水，如果有第 5 号桶，对应二进制为000 0101，那么就让 0 号和 2 号小猪去喝，以此类推，最终我们根据死的小猪的编号即可确定是哪个桶有毒药，举例来说就是如果 1、3、5、7 这四个小猪死了，那么就是101 0101(85)号桶含有毒药。

BitSet简介

其实在很多语言中都有位图算法得具体实现形式，例如在Java中，我们就可以通过使用BitSet很方便的去使用位图的思想，其中的set方法就对应着将指定位置为存在，get方法则返回指定位是否存在的布尔值结果，构造函数中的参数即对应着我们需要需要使用多少个位，并通过计算得到需要的long数组的长度，因此我们使用如下代码，就可以很方便的去使用我们之前位图的思想：

IntStream stream = new Random().ints(10000000, 1, 1000000);
BitSet set = new BitSet(100000000);
stream.forEach(set::set);
IntStream.range(1, 1000000)
        .filter(val -> !set.get(val))
        .forEach(System.out::println);

总结

本文主要讲解了位图的基本概念及具体使用方法，随后又讲解了Java中的一种位图实现：BitSet，时隔两个多月，终于写了这篇总结，其实一直也都想写了，只是觉得自己的理解不够深，可能无法给大家带来帮助，不过为了水一篇博客，就写了位运算系列的第三篇，以后有新的理解了，再修改吧，当然此系列也会持续更新的，就是不知道下次是什么时候了。