class 032 位图

🕗 发布于 2024-10-08 13:07 Java 算法 数据结构 位图

这篇文章是看了“左程云”老师在b站上的讲解之后写的, 自己感觉已经能理解了, 所以就将整个过程写下来了。

这个是“左程云”老师个人空间的b站的链接, 数据结构与算法讲的很好很好, 希望大家可以多多支持左程云老师, 真心推荐.

左程云的个人空间-左程云个人主页-哔哩哔哩视频 (bilibili.com)

在这里插入图片描述

1. 位图的原理

位图是一个类似于哈希表的“集合结构”,

哈希表可以放置不同的整数, 一个整数占据一个 int(32个bit位).无论是放 1 还是 10亿, 都是占据 32个bit位. 可以放置很多的数字,

位图和哈希表类似, 而且极大的节省了空间, 一个数字只占据 一个 bit位, 但是不能放置太多的数字, 而且要保证所有数字必须是一个连续的区间.

对比：在这里我们只是探讨(int)整数类型的.

数据要求：
1. 哈希表：不用是连续的整数, 任何数字都可以, 1, 3, 20亿. 任何数字都能随机加入哈希表.
2. 位图：必须是一段连续的整数比如：0 ~ 200万, 确定了之后不能有其余的数字加入位图. 要是我们只是加入 1 和 20亿 这两个数字, 使用位图, 这就需要创建一个很巨大的数组, 空间上反而不划算了, 所以需要一个连续的区间.
占据空间
1. 哈希表：一个数字占据一个 int(32个bit位) 空间
2. 位图：一个数字占据一个 bit位 空间. 极大地节省了空间.
效率高低
1. 哈希表：各种操作的平均时间复杂度是 O(1), 但是最坏情况有可能到达 O(n).
2. 位图：各种操作的时间复杂度是 O(1), 是确定的.

注意：位图在使用的之前, 必须要先给定范围, 比如给定的范围是：0 ~ 1000, 在初始化的时候就能确定范围了. 以后所有数字(0 ~ 1000)进来的时候就不会额外占据空间了, 加入我想要放入 1234 这个数字, 是不能放入的, 因为不在这个范围内.

1.1 原理实现

假设此时我们需要存储 0 ~ 100 之间的数字, 一个 int 类型有 32个bit位,
所以 32(int) * 4 == 128 > 100, 所以我们可以知道需要 4 个 int 类型来存储.

int：[a][b][c][d], 此时我们创建了 1 个 int 类型的数组, 长度为： 4 , 我们可以用来存储 1 ~ 100 之间的数字了, a(0 ~ 31), b(32 ~ 63), c(64 ~ 95), d(96 ~ 127). 这样就能进行存储了.

我们利用每一个 bit位, 要是 bit位 是 1 说明对应的数字存在, 是 0 就代表对应的数字不存在.

从这里就能看出来, 位图极大地节省了空间, 非常方便. 我们只是用了 int[4] 就表示好了.

1.2 如何找到对应的位置

我们还是按照上面的数据：我们创建一个数字 int[4], 下标是 0, 1, 2, 3.

假设我们要找一个数字 x 对应的位置, 应该让 x / 32 这样找到的就是对应的 int 位置.
如果找找到这个数字在 int位置 中对应的 bit 位, 就直接让 x % 32.

举一个具体例子：假设我们要找 66 这个数字,
我们先找到它在哪一个下标：66 / 32 == 2, 所以在下标为 2 的 int 位置.
然后我们找 66 在哪一个 bit位：66 % 32 == 2, 所以在第二个位置 我们认为还是0, 1, 2 所以是第二个位置.(说第三个位置也是可以的, 但是我们这里就为了统一就直接说第二个位置).\

在这里插入图片描述

2. 位图的各种操作的实现

2.1 位图的各种操作

在这里插入图片描述

2.2 位图各种操作的实现

2.2.1 位图的初始化(利用构造函数)

这个意味着位图的初始化, 先给我一个数字 n, 位图需要存储的范围是：[0, n - 1]. 举几个例子说明：

假设 n == 1, 需要存储的范围是：[0, 0] 那我需要有一个 int(32位) 类型的空间. 这是最低标准
假设 n == 2 , 需要存储的范围是：[0, 1] 那我也需要有一个 int(32位) 类型的空间.
假设 n == 32 , 需要存储的范围是：[0, 31] 那我也需要有一个 int(32位) 类型的空间.
假设 n == 33 , 需要存储的范围是：[0, 32] 那我也需要有两个 int(32位) 类型的空间. 因为我第一个 int 类型的只能存放 [0, 31], 必须开辟下一个 int 空间用来存储 32 这个整数.
所以 1 / 32(向上取整) == 1, 2 / 32(向上取整) == 1, 33 / 32(向上取整) == 2.

总结：我们需要向上取整.

向上取整用代码实现如下：

原理：只是涉及到 a 和 b 的值(前提是 a, b 都是非负数), 利用这个式子：(a+b-1)/b

要是 a == k * b + 小余数, 不管这个余数是多少, 之后进行 + (b - 1), 都能实现向上取整的效果.
要是 a == k * b, 也能实现向上取整的效果, 只是没有变化.(假设 a = b = 3, 此时 a/b == 1), 没有实现向上取整的必要和意义. 但是使用上面的式子：5/3 == 1, 和原来是一样的.

public int[] set;  
  
// n个数字 : 0~n-1public Bitset(int n) {  
    // a/b如果结果想向上取整，可以写成 : (a+b-1)/b    // 前提是a和b都是非负数  
    set = new int[(n + 31) / 32];  // 这样就足以支持 n - 1 个数字了.
}

2.2.2 位图的加入操作 `add` 函数

我们先要找到 num 这个数字在数组的哪一个下标(位置)中, 利用：num / 32.
然后寻找到在这个位置中的哪一个 bit位：利用 num % 32.
找到之后, 将这个 bit位 的 0 修改为 1.

举一个例子：

按照 8 个bit位来举例：
10101100 我们要将第 4 个位置的数字修改为 1 , 按照从右往左 0 ~ 31.
00010000 我们将 1 这个数字左移：(num % 32) 个 bit 位.
-------- | 进行“按位或”运算
10111100 这样就将“bit”位修改了.

实际操作代码如下：

public void add(int num) {  
    set[num / 32] |= 1 << (num % 32);  // 为了使代码更加简洁.
    // set[num / 32] 是数组中的下标, 第几个位置.
}

在这里插入图片描述

2.2.3 位图的删除操作 `remove` 函数

和 add 的操作是一样的,

我们先要找到 num 这个数字在数组的哪一个下标 (位置) 中, 利用：num / 32.
然后寻找到在这个位置中的哪一个 bit位：利用 num % 32.
找到之后, 将这个 bit位 的 1 修改为 0.

还是举一个例子：

按照 8 个bit位来举例：
10101100 我们要将第 3 个位置的数字修改为 0 , 按照从右往左 0 ~ 31.
00001000 我们将 1 这个数字左移：(num % 32) 个 bit 位.

11110111 这里我们将这个数字进行取反操作 ~(1 << (num % 32)).
10101100 和原来的数字进行 & 操作.
-------- &
10100100 这样就将数字 1 修改为：0.

实际操作代码如下：

注意：推荐使用这个方法, 虽然用 ^ 运算也能做, 但是有缺陷,

使用 & 运算：不用进行判断, 无论需要修改的位置是不是 0, 我都能将其修改为 0.
使用 ^ 运算：需要进行判断, 若是需要修改的位置是 0, 那就修改为了 1.(会出现错误), 所以推荐下面这个使用 & 运算的方法.

public void remove(int num) {  
    set[num / 32] &= ~(1 << (num % 32));  
}

2.2.4 位图的反转操作 `reverse` 函数

reverse 函数实现的是：

若是一个数字在位图中, 通过 reverse 函数消除这个数字, (将对应的 bit位 从 1 修改为 0)
若是一个数字不在位图中, 通过 reverse 函数添加这个数字, (将对应的 bit位 从 0 修改为 1)

这个需要注意的地方和 remove 中的一样, 已经说的很明白了.

举一个例子：

11110111 我们举一个极端一点的例子：我们需要修改的是第 3 个位置的 0.(假设这个位置是 0 即：没有这个数字).
00001000 我们将 1 这个数字左移：(num % 32) 个 bit 位.
-------- ^
11111111 这样就修改好了.

11111111 我们继续利用这个例子, 修改第 3 个位置的 1, (这个位置的数字是 1 即：有这个数字)
00001000 我们将 1 这个数字左移：(num % 32) 个 bit 位.
-------- ^
11110111 这样就修改好了.

实际操作代码如下：

public void reverse(int num) {  
    set[num / 32] ^= 1 << (num % 32);  
}

2.2.5 位图的检查 `contains` 函数

我们判断一个数字 num 在不在位图中, 只需要判断对应的 bit位 是 1 还是 0 就行了.

num / 32 和 num % 32 的意义就不说了,

有两种方法：

将对应数字的对应 bit位 向右移动到 0 位置, 然后和 1 进行 & 运算, 判断 结果是不是 == 1 就行
1. 对应的代码：((set[num / 32] >> (num % 32)) & 1) == 1.
将 1 向左移动到对应的需要判断的 bit位 位置, 然后进行 & 运算, 判断 结果是不是 != 0 就行.
1. 对应的代码：(set[num / 32] & (1 << (num % 32))) != 0.

public boolean contains(int num) {  
    return ((set[num / 32] >> (num % 32)) & 1) == 1;  
}

3. 对数器验证正确性

这里直接将所有的代码都打出来：

import java.util.HashSet;  
  
// 位图的实现  
// Bitset(int size)  
// void add(int num)  
// void remove(int num)  
// void reverse(int num)  
// boolean contains(int num)  
public class Code01_Bitset {  
  
    // 位图的实现  
    // 使用时num不要超过初始化的大小  
    public static class Bitset {  
       public int[] set;  
  
       // n个数字 : 0~n-1       public Bitset(int n) {  
          // a/b如果结果想向上取整，可以写成 : (a+b-1)/b          // 前提是a和b都是非负数  
          set = new int[(n + 31) / 32];  
       }  
  
       public void add(int num) {  
          set[num / 32] |= 1 << (num % 32);  
       }  
  
       public void remove(int num) {  
          set[num / 32] &= ~(1 << (num % 32));  
       }  
  
       public void reverse(int num) {  
          set[num / 32] ^= 1 << (num % 32);  
       }  
  
       public boolean contains(int num) {  
          return ((set[num / 32] >> (num % 32)) & 1) == 1;  
       }  
  
    }  
  
    // 对数器测试  
    public static void main(String[] args) {  
       int n = 1000;  
       int testTimes = 10000;  
       System.out.println("测试开始");  
       // 实现的位图结构  
       Bitset bitSet = new Bitset(n);  
       // 直接用HashSet做对比测试  
       HashSet<Integer> hashSet = new HashSet<>();  
       System.out.println("调用阶段开始");  
       for (int i = 0; i < testTimes; i++) {  
          double decide = Math.random();  
          // number -> 0 ~ n-1，等概率得到  
          int number = (int) (Math.random() * n);  
          if (decide < 0.333) {  
             bitSet.add(number);  
             hashSet.add(number);  
          } else if (decide < 0.666) {  
             bitSet.remove(number);  
             hashSet.remove(number);  
          } else {  
             bitSet.reverse(number);  
             if (hashSet.contains(number)) {  
                hashSet.remove(number);  
             } else {  
                hashSet.add(number);  
             }  
          }  
       }  
       System.out.println("调用阶段结束");  
       System.out.println("验证阶段开始");  
       for (int i = 0; i < n; i++) {  
          if (bitSet.contains(i) != hashSet.contains(i)) {  
             System.out.println("出错了!");  
          }  
       }  
       System.out.println("验证阶段结束");  
       System.out.println("测试结束");  
    }  
  
}

3.1 解释对数器的验证过程

提醒：对数器是一个极其重要的验证手段和 debug 练习方式, 所以一定要掌握, 一定要多熟悉, 多写对数器.

重点是解释对数器的验证过程：

原理是：使用哈希表和位图进行对比, 两个类能实现的功能是一样的, 所以只需要判断最后的结果是不是一样就行了.
首先设置 n 的范围, 然后设置 测试次数：testTimes. 创建位图和哈希表的实例
每一次测试都随机生成 number 的值(范围是：[0, 999]), 然后每一次都随机生成 decide 的值(范围是 [0, 1)).
然后根据 decide 的范围来判断执行哪一步操作. 这里我们设置的是,
1. 若是 < 0.333(近似约等于 1/3 的概率), 就将 number 同时加入哈希表和位图中.
2. 若是 >= 0.333 && < 0.666, 就将 number 从哈希表和位图中删除.
3. 若是 >= 0.666 < 1, 就执行位图的反转操作, hashset 内置函数中没有这个功能的函数, 自己实现就行了, 比如分为两种情况：先用 hashset 的 contains 函数判断是不是存在这个数字,
  1. 要是存在就删除.
  2. 要是不存在就加入.
然后进行验证过程：因为我们先设置的 n == 1000, 所以位图和哈希表中能进行存储的数字范围是：[0, 999], 所以对应的, 从 0 开始, 判断是不是存在于哈希表和位图中, 要是存在肯定是同时存在, 要是不存在肯定同时不存在, 因为返回的类型是 boolean类型, 所以只需要判断最后 true 和 false 能不能对上 就行.

4. 实现更多操作并且在线测试验证

在这里插入图片描述

// 位图的实现  
// Bitset是一种能以紧凑形式存储位的数据结构  
// Bitset(int n) : 初始化n个位，所有位都是0  
// void fix(int i) : 将下标i的位上的值更新为1  
// void unfix(int i) : 将下标i的位上的值更新为0  
// void flip() : 翻转所有位的值  
// boolean all() : 是否所有位都是1  
// boolean one() : 是否至少有一位是1  
// int count() : 返回所有位中1的数量  
// String toString() : 返回所有位的状态  
public class Code02_DesignBitsetTest {  
  
    // 测试链接 : https://leetcode-cn.com/problems/design-bitset/    
    class Bitset {  
       private int[] set;         // 初始化时需要使用的数组  
       private final int size;    // 判断到底要支持几个数字的查询, 在初始化的时候是多少, 后续就永远确定了.  
       private int zeros;         // 判断有几个不存在的：不存在的数字的数量  
       private int ones;          // 判断有几个存在的：存在的数字的数量  
       private boolean reverse;   // 是否整个位经历过反转.若是 reverse = false 说明：1 代表：存在, 0 代表：不存在.  
                                         // 若是 reverse = true 说明：1 代表：不存在, 0 代表：存在.  
                                         // 这样会非常方便, 不用整体进行遍历一遍修改.  
  
       public Bitset(int n) {  
          set = new int[(n + 31) / 32];  // 这个和原来一样, 还是向上取整.  
          size = n;            // 代表了可以进行 n 个数字的查询.  
          zeros = n;           // 因为最开始位图中全是：0, 所以设置为 n.          
          ones = 0;            // 因为最开始位图中全是：0, 所以设置为 0, 没有 1.          
          reverse = false;     // 此时没有经历过反转, 所以 reverse 是 false.       
          }  
  
       // 把i这个数字加入到位图  
       public void fix(int i) {  
          int index = i / 32;  
          int bit = i % 32;  
          if (!reverse) {  
             // 位图所有位的状态，维持原始含义  
             // 0 : 不存在  
             // 1 : 存在  
             if ((set[index] & (1 << bit)) == 0) { // 这里说明需要添加的位置 bit位 是：0.需要添加数字.  
                zeros--;   // 0 的数量要 “--”, 因为一个新的数字进来了.  
                ones++;    // 1 的数量要 “++”, 因为一个新的数字进来了.  
                set[index] |= (1 << bit);  
             }      // else 情况就说明 bits位 是 1, 不需要添加数字. 那就不用操作 else 情况了.  
          } else {   // 反转之后的情况.  
             // 位图所有位的状态，翻转了  
             // 0 : 存在  
             // 1 : 不存在  
             if ((set[index] & (1 << bit)) != 0) { // 说明这个 bit位 是 1, 不存在, 要将其修改为 0.
                zeros--;    // 注意, 我们这里是判断不存在的数量, 我们执行的操作是添加, 所以--.  
                ones++;     // 同样的, 我们这里执行的是添加操作, 所以要++.  
                set[index] ^= (1 << bit); // 我们前面已经有了判断, 这个 bit位 是 1, 所以要将其反转.  
             }  
          }  
       }  
  
       // 把i这个数字从位图中移除  
       public void unfix(int i) {  
          int index = i / 32;  
          int bit = i % 32;  
          if (!reverse) {  // 没有经历过反转.  
             if ((set[index] & (1 << bit)) != 0) {  
                ones--;  // 存在的-- 因为执行的是删除操作  
                zeros++; // 不存在的++, 因为执行的是删除操作.  
                set[index] ^= (1 << bit);  
             }  
          } else {         // 经历过反转.  
             if ((set[index] & (1 << bit)) == 0) {  
                ones--;   // 存在的-- 因为执行的是删除操作  
                zeros++;  // 不存在的++, 因为执行的是删除操作.  
                set[index] |= (1 << bit);  
             }  
          }  
       }  
  
       public void flip() {  
          reverse = !reverse;  // 直接进行反转, 省去了整个位图的遍历, 毕竟 reverse 不是 true 就是 false.          
          int tmp = zeros;  
          zeros = ones;  // 这里还需要交换 0 与 1 的值.(计数)的情况.  
          ones = tmp;  
       }  
  
       public boolean all() {  
          return ones == size; // 直接判断 1 的数量是不是等于 size.       
        }  
  
       public boolean one() {  
          return ones > 0; // 只要确定有一个位置上有 1 就行了,  
       }  
  
       public int count() {  
          return ones;    // 判断存在中的数字有几个, 直接返回 1 的个数.  
       }  
  
  
       // 这个方法就是将数组中所有的 bit位上的1 都拼起来, 拿出来一个下标为 0, 1, 2, 3 ... n 就开始拼就行.  
       public String toString() {  
          StringBuilder builder = new StringBuilder();  
          for (int i = 0, k = 0, number, status; i < size; k++) { // k 表示拿到了第一个整数.  
             number = set[k];  
             for (int j = 0; j < 32 && i < size; j++, i++) {  
                status = (number >> j) & 1;  // 将每一个状态都进行判断.  
                status ^= reverse ? 1 : 0;  // 需要判断 reverse 是 true 还是 false. 若是true, 需要统计 0, 若是 false 直接统计 1.                
                builder.append(status);  
             }  
          }  
          return builder.toString();  
       }  
    }  
  
}

原文地址：https://blog.csdn.net/2301_80967814/article/details/142745277

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：@Transactional声明式事务回调编程
下一篇：将 GitHub 仓库从公开（public）设置为私有（private）

【论文速看】DL最新进展20241008-多模态、医学图像分割、扩散模型
【论文速看】DL最新进展20241008-多模态、医学图像分割、扩散模型
阅读更多2024-10-09
计算机毕业设计基于Flask+vue的博客系统的设计与实现 Python毕业设计 Python毕业设计选题 Flask框架 Vue【附源码+安装调试】
基于Flask+Vue的博客系统是一个现代化的内容分享平台，提供文章管理、公告资讯、平台沟通等功能。系统旨在提升用户体验，丰富功能模块，加强社交互动，并提供个性化服务。管理员可以通过后台管理模块高效地
阅读更多2024-10-09
胤娲科技：机械臂「叛逃」记——自由游走，再悄然合体
在完成了抓取任务后，这款机械臂还能调整自己的姿势，用剩下的手指“爬”回来，与手臂重新合体。此刻的你，是否幻想过有一只无形的手，轻盈地飘过，帮你熄灭那盏碍眼的灯？机械臂的“叛逃”之旅，不仅让我们见证了科
阅读更多2024-10-09
微知-如何通过systemctl查看是否存在某个服务？如何全局查看所有的服务？（systemctl list-units --type=service，）
本文介绍在某些场景需要查看是否启动某个服务，
阅读更多2024-10-09
Excel转pdf
注意，以上示例代码中的input.xlsx是输入的Excel文件名，output.pdf是输出的PDF文件名。Java可以使用Apache POI和iText两个库来实现Excel转PDF的功能。pd
阅读更多2024-10-09
linux中的火墙优化策略
1.火墙介绍1.火墙介绍1.netfilter2.iptables3.iptablesfirewalld。
阅读更多2024-10-09
互斥锁、原子锁、自旋锁
在选择锁的类型时，需要根据具体的应用场景和性能要求来决定使用哪种锁。在某些情况下，可能会结合使用多种锁，例如，使用互斥锁保护共享资源，同时使用原子锁保证某些操作的原子性。多线程编程中，锁是一种同步机制
阅读更多2024-10-09
Docker基本操作命令（一）
Docker 是一个开源的容器化平台，用于自动化部署应用程序。它允许开发者将应用及其依赖打包在轻量级的容器中，实现环境一致性并简化配置。Docker 容器在隔离的环境中运行，独立于主机系统，也相互隔离
阅读更多2024-10-09
NeRF2: Neural Radio-Frequency Radiance Fields 笔记
任务：用 NeRF 对无线信号的传播进行建模，建模完成后可以用NeRF网络生成新位置下的信号。生成的信号用于指纹定位、信道估计等下游任务。
阅读更多2024-10-09
学生家长必备，中小学课本教材电子书批量下载工具
今天再整理更新几个最新的电子书教材网站和下载工具苏生不惑备用号，分享各种黑科技软件资源和技巧，带你玩转互联网。首先还是国家中小学智慧教育平台这个网站还有在线电子教材网站 http://www.haod
阅读更多2024-10-09

class 032 位图

1. 位图的原理

1.1 原理实现

1.2 如何找到对应的位置

2. 位图的各种操作的实现

2.1 位图的各种操作

2.2 位图各种操作的实现

2.2.1 位图的初始化(利用构造函数)

2.2.2 位图的加入操作 add 函数

2.2.3 位图的删除操作 remove 函数

2.2.4 位图的反转操作 reverse 函数

2.2.5 位图的检查 contains 函数

3. 对数器验证正确性

3.1 解释对数器的验证过程

4. 实现更多操作并且在线测试验证

相关文章

2.2.2 位图的加入操作 `add` 函数

2.2.3 位图的删除操作 `remove` 函数

2.2.4 位图的反转操作 `reverse` 函数

2.2.5 位图的检查 `contains` 函数