一，位图介绍
位图（Bitmap）是一种用于存储图像的方式，它通过二维矩阵（由像素组成）来表示图像的每一个细节。每个像素通常对应一个特定的颜色值，位图的每个“位”就代表了图像的一个像素。
位图的基本概念
- 像素（Pixel）：位图图像是由无数个像素组成的，每个像素有一个颜色值。像素是图像中最小的显示单元。
- 颜色深度：位图的颜色深度决定了每个像素可以表示的颜色数。常见的颜色深度有8位、16位、24位、32位等。颜色深度越高，每个像素可以表示的颜色种类就越多，图像就越细腻。
- 分辨率：图像的分辨率表示图像的宽度和高度，以像素为单位。例如，1920x1080的分辨率意味着图像宽度为1920像素，高度为1080像素。
- 文件大小：位图的文件大小通常和图像的分辨率、颜色深度以及压缩方式有关。没有压缩的位图（如BMP文件）通常文件较大。
位图文件格式
常见的位图文件格式有：
- BMP（Bitmap Image File）：最基础的位图格式，不压缩，文件较大，但图像质量保持完好。
- PNG（Portable Network Graphics）：无损压缩格式，常用于网页和图形应用，支持透明背景。
- JPEG（Joint Photographic Experts Group）：有损压缩格式，常用于照片和图像，能够显著减少文件大小，但可能牺牲图像质量。
- GIF（Graphics Interchange Format）：常用于动画，支持256色的图像，支持透明和动画效果。
- TIFF（Tagged Image File Format）：用于高质量图像存储，支持无损压缩和多页图像。
位图的优缺点
优点：
- 精度高：由于每个像素单独存储，位图能够表现非常详细的图像细节。
- 简单易用：处理位图的算法通常较为简单，适用于需要精确控制图像像素的应用。
缺点：
- 文件大小大：位图不经过压缩时文件非常大，不适合存储高分辨率的图像。
- 不适合缩放：位图图像在缩放时容易失真，特别是放大时，可能会出现模糊或锯齿状。
位图与矢量图的对比
- 位图：图像由像素构成，适合表现细腻的图像（如照片），不适合缩放和改变分辨率。
- 矢量图：图像由路径、点和线构成，适合用于插图和图形设计，放大或缩小时不会失真。
位图的应用
位图广泛应用于：
- 数字摄影：大多数数字相机和手机拍摄的照片都是位图格式。
- 网页设计：许多网页图像和图标使用PNG、JPEG等位图格式。
- 图像编辑：例如Photoshop等图像编辑软件，处理的通常是位图图像。
- 图形显示：例如显示屏、打印机等设备的图像输出通常是位图形式。
总结
位图是一种通过像素矩阵来表达图像的方式，适合存储高质量的图像，广泛应用于数字图像处理、网页设计、摄影等领域。它的文件大小较大，不适合于图像的频繁缩放，而矢量图则在这方面表现得更好。
二，使用位图实现哈希表
1，原理
因为1个int类型含有4个字节，有32个bit，使用每个bit位上0和1的状态来表示该数字是否加入表中，但这就要求哈希表是只能存储连续数字。
2，补充
1）怎么向上取整
已知计算机里只有向下取整，如：2 / 3 = 0；4 / 3 = 1；6 / 3 = 2；
但向下取整是 2 / 3 = 1；3 / 3 = 1；如果想通过a / b + 1来实现是不可能的，因为如果a = b的话就不对了。
所以采用（a + b - 1）/ b ，因为如果a 除 b 后还有余数，b - 1可以让余数升到下一位从而结果加1，如果没有余数也不会影响结果。
三，对数器验证
1，如何随机生成0到1的小数
2，错误展示
else
{bitset.flip_num(number);if (hashset.find(number) != hashset.end()){hashset.insert(number);}
}
这里if操作错误，找到后应该删去，同时缺少没有找到后插入该数字。
3，代码
#include<iostream>
#include<random>
#include<unordered_set>using namespace std;
random_device rd;
default_random_engine gen(rd());
uniform_real_distribution<double> probability(0.0, 1.0);struct Bitset
{
public:int* bitset;int len;Bitset(int x) : len((x + 31) / 32){bitset = new int[len];}void add_num(int n){bitset[n / 32] |= 1 << (n % 32);}void remove_num(int n){bitset[n / 32] &= ~(1 << (n % 32));}void flip_num(int n){bitset[n / 32] ^= 1 << (n % 32);}//翻转的意思是原来数组有就变为没有，如果原来没有现在变为有。bool find_num(int n){return ( (bitset[n / 32] >> (n % 32)) & 1 ) == 1;}};void Test_machine(Bitset& bitset,int test_times,int len)
{uniform_int_distribution<int> dis(0, len - 1);unordered_set<int> hashset;double chance;int number;cout << "测试开始" << endl;bitset.add_num(5);hashset.insert(5);if (bitset.find_num(5) != (hashset.find(5) != hashset.end())){cout << "出错了" << endl;}cout << "调用阶段开始" << endl;for (int i = 0; i < test_times; i++){chance = probability(gen);number = dis(gen);if (chance < 0.33){bitset.add_num(number);hashset.insert(number);}else if (chance < 0.66){bitset.remove_num(number);hashset.erase(number);}else{bitset.flip_num(number);if (hashset.find(number) != hashset.end()){hashset.erase(number);}else{hashset.insert(number);}}}cout << "调用阶段结束" << endl;cout << "验证阶段开始" << endl;for (int i = 0; i < len; i++){if (bitset.find_num(i) != (hashset.find(i) != hashset.end())){cout<<"出错了"<<endl;}}cout << "验证阶段结束" << endl << "测试结束" << endl;
}int main()
{Bitset bitset(20);Test_machine(bitset, 10, 20);return 0;
}四，补充题
题目
代码
#include<iostream>struct Bitset
{
public:int* bitset;int size;int zeros, ones;bool reverse = false;Bitset(int n) :size(n) {zeros = size;ones = 0;bitset = new int[(size + 31) / 32];}void fix(int i){int index = i / 32;int bit = i % 32;if (!reverse)//在bitset未被翻转时，reverse是false。//此时0代表不存在，1代表存在。{if ((bitset[index] & 1 << bit) == 0){zeros--;ones++;bitset[index] ^= 1 << bit;}}else//如果bitset被翻转，则reverse是true//此时0代表存在，1代表不存在。//使用reverse是为了翻转时不必遍历每一位。{if ((bitset[index] & 1 << bit) != 0){zeros--;ones++;bitset[index] ^= 1 << bit;}}}void flip(){reverse = !reverse;int temp;temp = zeros;zeros = ones;ones = temp;}bool all(){return ones == size;}bool one(){return ones > 0;}int count_ones(){return ones;}
};